• 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 - No 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 (687.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
Adler, Isolde
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sintiari, Ni Luh Dewi
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
    Constructive algorithm for path-width of matroids 
    Jeong, Jisu; Kim, Eun Jung; Oum, Sang-il (2016) Communication / Conférence
  • Thumbnail
    Valued-Based Argumentation for Tree-like Value Graphs 
    Kim, Eun Jung; Ordyniak, Sebastian (2012) Chapitre d'ouvrage
  • 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