A graph $G$ with a perfect matching is Pfaffian if it admits an orientation $D$ such that every central cycle $C$ (i.e. $C$ is of even size and $G-V(C)$ has a perfect matching) has an odd number of edges oriented in either direction of the cycle. It is known that the number of perfect matchings of a Pfaffian graph can be computed in polynomial time. In this paper, we show that every embedding of a Pfaffian brace (i.e. 2-extendable bipartite graph) on a surface with a positive genus has face-width at most 3. Further, we study Pfaffian cubic braces and obtain a characterization of Pfaffian polyhex graphs: a polyhex graph is Pfaffian if and only if it is either non-bipartite or isomorphic to the cube, or the Heawood graph, or the Cartesian product $C_k\times K_2$ for even integers $k\ge 6$.
@article{10_37236_3540,
author = {Dong Ye and Heping Zhang},
title = {Face-width of {Pfaffian} braces and polyhex graphs on surfaces},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/3540},
zbl = {1305.05196},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3540/}
}
TY - JOUR
AU - Dong Ye
AU - Heping Zhang
TI - Face-width of Pfaffian braces and polyhex graphs on surfaces
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/3540/
DO - 10.37236/3540
ID - 10_37236_3540
ER -
%0 Journal Article
%A Dong Ye
%A Heping Zhang
%T Face-width of Pfaffian braces and polyhex graphs on surfaces
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/3540/
%R 10.37236/3540
%F 10_37236_3540
Dong Ye; Heping Zhang. Face-width of Pfaffian braces and polyhex graphs on surfaces. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/3540
