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.
Community of mathematics and fundamental computer science in Lyon; Funder: French National Research Agency (ANR); Code: ANR-10-LABX-0070
PROJET AVENIR LYON SAINT-ETIENNE; Funder: French National Research Agency (ANR); Code: ANR-11-IDEX-0007
Forbidden Structures; Funder: French National Research Agency (ANR); Code: ANR-13-BS02-0007
Graph theory and mathematical programming with applications in chemistry and computer science; Funder: Ministry of Education, Science and Technological Development of Republic of Serbia; Code: 174033
Structure of Hereditary Graph Classes and Its Algorithmic Consequences; Funder: UK Research and Innovation; Code: EP/N019660/1