标题： 关于无偶环图的秩宽 显示英文标题

标题： On rank-width of even-hole-free graphs

摘要： 我们提出了一类无clique cutset的(diamond, even hole)-free图，其rank-width是无界的。 一般来说，even-hole-free图具有无界的rank-width，因为chordal图是even-hole-free的。 A.A. da Silva, A. Silva和C. Linhares-Sales（2010）表明，平面even-hole-free图具有有界的rank-width，而N.K. Le（2016）表明，无star cutset的even-hole-free图具有有界的rank-width。 一个自然的问题是，询问无clique cutset的even-hole-free图是否具有有界的rank-width。 我们的结果给出了否定的答案。 因此，我们不能应用Courcelle和Makowsky的元定理，该定理将为大量问题提供高效的算法，包括最大独立集问题，其复杂性对于(diamond, even hole)-free图仍然未解决。 显示英文摘要

摘要： 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 even-hole-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 Courcelle and Makowsky's meta-theorem 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.