On rank-width of (diamond, even-hole)-free graphs

zbMATH Open1400.05232arXiv1611.09907MaRDI QIDQ4558968FDOQ4558968

Authors: Isolde Adler, Ngoc Khang Le, Haiko Müller, Kristina Vušković, Marko Radovanović, Nicolas Trotignon 

Publication date: 30 November 2018

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1611.09907

Recommendations

• On the tree-width of even-hole-free graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Bounding clique-width via perfect graphs

zbMATH Keywords

clique-widthrank-widtheven-hole-free graphclique cutset(diamond, even hole)-free graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cited In (6)

• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Colouring square-free graphs without long induced paths
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• Rank-width and tree-width of \(H\)-minor-free graphs
• A class of graphs with large rankwidth
• Graphs with polynomially many minimal separators

This page was built for publication: On rank-width of (diamond, even-hole)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558968)