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

dmtcs:2575 - Discrete Mathematics & Theoretical Computer Science, October 5, 2017, Vol. 19 no. 1 - https://doi.org/10.23638/DMTCS-19-1-24
On rank-width of even-hole-free graphsArticle

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

    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.


    Volume: Vol. 19 no. 1
    Section: Graph Theory
    Published on: October 5, 2017
    Accepted on: August 3, 2017
    Submitted on: August 1, 2017
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05C85,G.2.2
    Funding:
      Source : OpenAIRE Graph
    • PROJET AVENIR LYON SAINT-ETIENNE; Funder: French National Research Agency (ANR); Code: ANR-11-IDEX-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
    • Community of mathematics and fundamental computer science in Lyon; Funder: French National Research Agency (ANR); Code: ANR-10-LABX-0070
    • Structure of Hereditary Graph Classes and Its Algorithmic Consequences; Funder: UK Research and Innovation; Code: EP/N019660/1
    • Forbidden Structures; Funder: French National Research Agency (ANR); Code: ANR-13-BS02-0007

    Consultation statistics

    This page has been seen 840 times.
    This article's PDF has been downloaded 368 times.