Geodesic
On rank-width of even-hole-free graphs
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2017_19_1_a20,
     author = {Adler, Isolde and Le, Ngoc Khang and M\"uller, Haiko and Radovanovi\'c, Marko and Trotignon, Nicolas and Vu\v{s}kovi\'c, Kristina},
     title = {On rank-width of even-hole-free graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-24},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-24/}
}
TY  - JOUR
AU  - Adler, Isolde
AU  - Le, Ngoc Khang
AU  - Müller, Haiko
AU  - Radovanović, Marko
AU  - Trotignon, Nicolas
AU  - Vušković, Kristina
TI  - On rank-width of even-hole-free graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-24/
DO  - 10.23638/DMTCS-19-1-24
LA  - en
ID  - DMTCS_2017_19_1_a20
ER  - 
%0 Journal Article
%A Adler, Isolde
%A Le, Ngoc Khang
%A Müller, Haiko
%A Radovanović, Marko
%A Trotignon, Nicolas
%A Vušković, Kristina
%T On rank-width of even-hole-free graphs
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-24/
%R 10.23638/DMTCS-19-1-24
%G en
%F DMTCS_2017_19_1_a20
Adler, Isolde; Le, Ngoc Khang; Müller, Haiko; Radovanović, Marko; Trotignon, Nicolas; Vušković, Kristina. On rank-width of even-hole-free graphs. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi : 10.23638/DMTCS-19-1-24. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-24/

Cité par Sources :