Decomposition of even-hole-free graphs with star cutsets and 2-joins
Decomposition of even-hole-free graphs with star cutsets and 2-joins
复制标题
具有星割集和 2-连接的偶孔无图分解
DOI：
10.1016/j.jctb.2012.10.001
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Da Silva M
中科院分区：
文献类型：
--
作者：
Da Silva M
在本文中，我们考虑通过排除偶数孔（即偶数长度的无弦循环）作为诱导子图而定义的简单图类。这些图被称为无偶孔图。我们证明了偶无洞图的分解定理，该定理使用星割集和 2-连接。这是对 Conforti、Cornuéjols、Kapoor 和 Vušković 提出的唯一其他先前已知的无偶孔图分解的显着强化，该分解使用 2-连接和星形、双星形和三星形割集。它也类似于 Chudnovsky、Robertson、Seymour 和 Thomas 用斜割集、2-连接及其补集对 Berge（即完美）图进行分解。无偶孔图和 Berge 图之间的相似性高于无偶孔图和简单的无奇孔图之间的相似性，因为排除 4 孔会自动排除长度至少为 6 的所有反孔。在不包含 4 孔的图中，斜割集简化为星割集，补集中的 2-连接意味着星割集，因此在某种程度上，期望无偶孔图可以仅用星割集和 2-连接来分解。该分解定理的结果是偶数无洞图的识别算法，该算法比以前已知的算法要快得多。
In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We prove a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornuéjols, Kapoor and Vušković, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. The similarity between even-hole-free graphs and Berge graphs is higher than the similarity between even-hole-free graphs and simply odd-hole-free graphs, since excluding a 4-hole, automatically excludes all antiholes of length at least 6. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is a recognition algorithm for even-hole-free graphs that is significantly faster than the previously known ones.
登录
查看更多内容
平衡0-1矩阵一、分解
DOI：
--
发表时间：
2001
期刊：
J. Comb. Theory B
影响因子：
--
作者：
M. Conforti;Gérard Cornuéjols;Ajai Kapoor;Kristina Vuskovic
通讯作者：
Kristina Vuskovic
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
Da Silva;Murilo Vicente Gonçalves
通讯作者：
Murilo Vicente Gonçalves
为没有平衡倾斜分区的完美图形着色
DOI：
10.48550/arxiv.1308.6444
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Chudnovsky M
通讯作者：
Chudnovsky M
关于桥接图的直径和半径
影响因子：
0.8
作者：
M. Farber
通讯作者：
M. Farber
贝塔完美图
DOI：
--
发表时间：
1996
期刊：
J. Comb. Theory B
影响因子：
--
作者：
S. Markossian;G. Gasparian;B. Reed
通讯作者：
B. Reed