• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

On the tree-width of even-hole-free graphs

Aboulker, Pierre; Adler, Isolde; Kim, Eun Jung; Sintiari, Ni Luh Dewi; Trotignon, Nicolas (2021), On the tree-width of even-hole-free graphs. https://basepub.dauphine.psl.eu/handle/123456789/22211

View/Open
2008.05504.pdf (377.7Kb)
Type
Document de travail / Working paper
Date
2021
Series title
Preprint Lamsade
Published in
Paris
Metadata
Show full item record
Author(s)
Aboulker, Pierre
Ecole Normale Supérieure
Adler, Isolde
School of Computing [Leeds]
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sintiari, Ni Luh Dewi
ENS Lyon, Université de Lyon
Trotignon, Nicolas
Abstract (EN)
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, K4)-free graphs was constructed, that still has unbounded tree-width [Sintiari and Trotignon, 2019]. The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary. We prove that for every graph G, if G excludes a fixed graph H as a minor, then G either has small tree-width, or G contains a large wall or the line graph of a large wall as induced subgraph. This can be seen as a strengthening of Robertson and Seymour's excluded grid theorem for the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a more general class: (theta, prism)-free graphs. This implies the known result that planar even hole-free graph have bounded tree-width [da Silva and Linhares Sales, Discrete Applied Mathematics 2010]. We conjecture that even-hole-free graphs of bounded degree have bounded tree-width. If true, this would mean that even-hole-freeness is testable in the bounded-degree graph model of property testing. We prove the conjecture for subcubic graphs and we give a bound on the tree-width of the class of (even hole, pyramid)-free graphs of degree at most 4.
Subjects / Keywords
Even-hole-free graphs; grid theorem; tree-width; bounded-degree graphs; property testing

Related items

Showing items related by title and author.

  • Thumbnail
    Twin-width VI: the lens of contraction sequences 
    Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan (2022) Communication / Conférence
  • Thumbnail
    EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs 
    Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié
  • Thumbnail
    Valued-Based Argumentation for Tree-like Value Graphs 
    Kim, Eun Jung; Ordyniak, Sebastian (2012) Chapitre d'ouvrage
  • Thumbnail
    Constructive algorithm for path-width of matroids 
    Jeong, Jisu; Kim, Eun Jung; Oum, Sang-il (2016) Communication / Conférence
  • Thumbnail
    Grundy Coloring & Friends, Half-Graphs, Bicliques 
    Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2020) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo