Minimally non-Pfaffian graphs
Minimally non-Pfaffian graphs
复制标题
DOI：
10.1016/j.jctb.2007.12.005
复制
发表时间：
2008-09
期刊：
影响因子：
--
通讯作者：
Sergey Norin;R. Thomas
中科院分区：
文献类型：
--
作者：
Sergey Norin;R. Thomas
我们考虑的问题，表征Pfweenan图。我们展示了一个无限的家庭非Pfronean图最小的匹配小关系。这与双方的情况形成鲜明对比，因为Little [C.H.C. Little，可转换（0，1）-矩阵的特征，J. Combin. Theory Ser. B 18（1975）187-208]证明了每个二部非Pfiranan图都包含一个同构于K 3，3的匹配子图。我们放松的概念，一个匹配的未成年人和猜想，只有100多（也许只有两个）非Pfiran图最小的关于这个概念。本文的第二部分定义了Pfalan因子临界图并对其进行了研究。他们似乎是有趣的，因为在Pfiran因子临界图中的近完美匹配的数量可以在多项式时间内计算。我们给出了这类图的多项式时间识别算法，并利用禁止中心子图刻画了非Pfiran因子临界图。
We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion. We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.