On rank-width of (diamond, even-hole)-free graphs
From MaRDI portal
Publication:4558968
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.
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
Cited in
(6)- (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
- Graphs with polynomially many minimal separators
- Rank-width and tree-width of \(H\)-minor-free graphs
- Colouring square-free graphs without long induced paths
- A class of graphs with large rankwidth
- (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
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)
