Ju l 2 01 7 On rank-width of ( diamond , even hole )-free graphs
Ju l 2 01 7 On rank-width of ( diamond , even hole )-free graphs
复制标题
Jul l 2 01 7 关于（菱形，偶孔）无图的等级宽度
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
Isolde Adler;N. Le;H. Müller;M. Radovanović;Nicolas Trotignon;Kristina Vuskovic
本文给出了一类无团割集且秩宽无界的无（钻石，偶洞）图。一般来说，无偶洞图的秩宽是无界的，因为弦图是无偶洞的。A.A. da Silva，A. Silva和C. Linhares-Sales（2010）证明了平面无偶洞图具有有界的秩宽，并且N.K. Le（2016）证明了不含星星割集的无偶洞图具有有界的秩宽度。一个自然的问题是问，是否偶洞无图没有团割集有界的秩宽度。我们的结果给出了否定的答案。因此，我们不能应用Courcelle，Makowsky和Rotics的元定理，这将为大量问题提供有效的算法，包括最大独立集问题，其复杂性仍然开放（钻石，甚至洞）-无图。
We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C. Linhares-Sales (2010) showed that planar even-hole-free graphs have bounded rank-width, and N.K. Le (2016) showed that evenhole-free graphs with no star cutset have bounded rank-width. A natural question is to ask, whether even-hole-free graphs with no clique cutsets have bounded rank-width. Our result gives a negative answer. Hence we cannot apply the meta-theorem by Courcelle, Makowsky and Rotics, which would provide efficient algorithms for a large number of problems, including the maximum independent set problem, whose complexity remains open for (diamond, even hole)-free graphs.
具有星割集和 2-连接的偶孔无图分解
DOI：
10.1016/j.jctb.2012.10.001
发表时间：
2013
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Da Silva M
通讯作者：
Da Silva M
DOI：
10.48550/arxiv.1205.2535
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Aboulker P
通讯作者：
Aboulker P