Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/206
Title: On rank-width of (diamond, even hole)-free graphs
Authors: Adler, Isolde
Le, Ngoc Khang
Müller, Haiko
Radovanović, Marko 
Trotignon, Nicolas
Vušković, Kristina
Affiliations: Algebra and Mathematical Logic 
Keywords: (Diamond, even hole)-free graph;Clique cutset;Clique-width;Even-hole-free graph;Rank-width
Issue Date: 1-Jan-2017
Journal: Discrete Mathematics and Theoretical Computer Science
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 the meta-theorem by Courcelle, Makowsky and Rotics, 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.
URI: https://research.matf.bg.ac.rs/handle/123456789/206
ISSN: 14627264
DOI: 10.23638/DMTCS-19-1-24
Appears in Collections:Research outputs

Show full item record

SCOPUSTM   
Citations

6
checked on Dec 24, 2024

Page view(s)

21
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.