
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
Type
Document de travail / Working paperDate
2021Series title
Preprint LamsadePublished in
Paris
Metadata
Show full item recordAuthor(s)
Aboulker, PierreEcole 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 testingRelated items
Showing items related by title and author.
-
Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2020) Communication / Conférence
-
Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2023) Article accepté pour publication ou publié
-
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Oum, Sang-Il (2023) Article accepté pour publication ou publié
-
Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan (2022) Communication / Conférence
-
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é