Adler, Isolde and Le, Ngoc Khang and Müller, Haiko and Radovanović, Marko and Trotignon, Nicolaset al. - On rank-width of even-hole-free graphs

dmtcs:3827 - Discrete Mathematics & Theoretical Computer Science, October 5, 2017, Vol 19 no. 1
On rank-width of even-hole-free graphs

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

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.


Source : oai:arXiv.org:1611.09907
Volume: Vol 19 no. 1
Section: Graph Theory
Published on: October 5, 2017
Submitted on: August 1, 2017
Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05C85,G.2.2


Share

Browsing statistics

This page has been seen 45 times.
This article's PDF has been downloaded 16 times.