Show simple item record

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

hal.structure.identifierEcole Normale Supérieure
dc.contributor.authorAboulker, Pierre
hal.structure.identifierSchool of Computing [Leeds]
dc.contributor.authorAdler, Isolde
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
hal.structure.identifierENS Lyon, Université de Lyon
dc.contributor.authorSintiari, Ni Luh Dewi
dc.contributor.authorTrotignon, Nicolas
dc.date.accessioned2021-11-16T10:55:58Z
dc.date.available2021-11-16T10:55:58Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22211
dc.language.isoenen
dc.subjectEven-hole-free graphsen
dc.subjectgrid theoremen
dc.subjecttree-widthen
dc.subjectbounded-degree graphsen
dc.subjectproperty testingen
dc.subject.ddc005en
dc.titleOn the tree-width of even-hole-free graphsen
dc.typeDocument de travail / Working paper
dc.description.abstractenThe 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.en
dc.publisher.cityParisen
dc.relation.ispartofseriestitlePreprint Lamsadeen
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.date.updated2021-11-16T10:53:48Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
2008.05504.pdf
Size:
377.7Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record