2007 | OriginalPaper | Chapter
Regular Coronoids and Ear Decompositions of Plane Elementary Bipartite Graphs
Author : Heping Zhang
Published in: Discrete Geometry, Combinatorics and Graph Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A connected bipartite graph is called
elementary
(or
normal
) if its every edge is contained in some perfect matching. In
rho
classification of coronoids due to Cyvin et al., normal coronoids are divided into two types: regular and half essentially disconnected. A coronoid is called
regular
if it can be generated from a single hexagon by a series of normal additions of hexagons (modes
L
1
,
L
3
or
L
5
) plus corona condensations of hexagons of modes
L
2
or
A
2
. Chen and Zhang (1997) gave a complete characterization: A coronoid is regular if and only if it has a perfect matching
M
such that the boundaries of non-hexagon faces are all
M
-alternating cycles. In this article, a general concept for the regular addition of an allowed face is proposed and the above result is extended to a plane elementary bipartite graph some specified faces of which are forbidden by applying recently developed matching theory. As its corollary, we give an equivalent definition of regular coronoids as a special ear decomposition.