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
TypeDocument de travail / Working paper
Series titlePreprint Lamsade
MetadataShow full item record
Ecole Normale Supérieure
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
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 / KeywordsEven-hole-free graphs; grid theorem; tree-width; bounded-degree graphs; property testing
Showing items related by title and author.
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é