id: 06109933
dt: j
an: 06109933
au: Che, Zhongyuan; Chen, Zhibo
ti: Forcing faces in plane bipartite graphs. II.
so: Discrete Appl. Math. 161, No. 1-2, 71-80 (2013).
py: 2013
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: forcing edge; forcing face; handle; perfect matching; plane elementary
    bipartite graph; $Z$-transformation graph
ci: 
li: doi:10.1016/j.dam.2012.08.016
ab: Summary: The concept of forcing faces of a plane bipartite graph was first
    introduced in the first part of this work [the authors, Discrete Math.
    308, No. 12, 2427‒2439 (2008; Zbl 1168.05357)], which is a natural
    generalization of the concept of forcing hexagons of a hexagonal system
    introduced by the authors in [“Forcing hexagons in hexagonal
    systems", MATCH Commun. Math. Comput. Chem. 56, No. 3, 649‒668 (2006;
    Zbl 1119.05322)]. In this paper, we further extend this concept from
    finite faces to all faces (including the infinite face) as follows: A
    face $s$ (finite or infinite) of a 2-connected plane bipartite graph
    $G$ is called a forcing face if the subgraph $G - V(s)$ obtained by
    removing all vertices of $s$ together with their incident edges has
    exactly one perfect matching. For a plane elementary bipartite graph
    $G$ with more than two vertices, we give three necessary and sufficient
    conditions for $G$ to have all faces forcing. We also give a new
    necessary and sufficient condition for a finite face of $G$ to be
    forcing in terms of bridges in the $Z$-transformation graph $Z(G)$ of
    $G$. Moreover, for the graphs $G$ whose faces are all forcing, we
    obtain a characterization of forcing edges in $G$ by using the notion
    of handle, from which a simple counting formula for the number of
    forcing edges follows.
rv: