TY - JOUR

T1 - Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree

AU - Abrishami, Tara

AU - Chudnovsky, Maria

AU - Vušković, Kristina

N1 - Funding Information:
Supported by NSF Grant DMS-1763817 and NSF-EPSRC Grant DMS-2120644.Supported by NSF Grant DMS-1763817. This material is based upon work supported by, or in part by, the U.S. Army Research Laboratory and the Army Research Office under grant number W911NF-16-1-0404.Partially supported by EPSRC grant EP/N0196660/1.
Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2022/11

Y1 - 2022/11

N2 - Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewidth k if it can be decomposed by a sequence of noncrossing cutsets of size at most k into pieces of size at most k+1. The study of hereditary graph classes (i.e. those closed under vertex deletion only) reveals a different picture, where cutsets that are not necessarily bounded in size (such as star cutsets, 2-joins and their generalization) are required to decompose the graph into simpler pieces that are structured but not necessarily bounded in size. A number of such decomposition theorems are known for complex hereditary graph classes, including even-hole-free graphs, perfect graphs and others. These theorems do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by them are far from being noncrossing. They are also of limited use in algorithmic applications. We show that in the case of even-hole-free graphs of bounded degree the cutsets described in the previous paragraph can be partitioned into a bounded number of well-behaved collections. This allows us to prove that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker et al. (2021) [1]. As a consequence, it follows that many algorithmic problems can be solved in polynomial time for this class, and that even-hole-freeness is testable in the bounded degree graph model of property testing. In fact we prove our results for a larger class of graphs, namely the class of C4-free odd-signable graphs with bounded degree.

AB - Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewidth k if it can be decomposed by a sequence of noncrossing cutsets of size at most k into pieces of size at most k+1. The study of hereditary graph classes (i.e. those closed under vertex deletion only) reveals a different picture, where cutsets that are not necessarily bounded in size (such as star cutsets, 2-joins and their generalization) are required to decompose the graph into simpler pieces that are structured but not necessarily bounded in size. A number of such decomposition theorems are known for complex hereditary graph classes, including even-hole-free graphs, perfect graphs and others. These theorems do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by them are far from being noncrossing. They are also of limited use in algorithmic applications. We show that in the case of even-hole-free graphs of bounded degree the cutsets described in the previous paragraph can be partitioned into a bounded number of well-behaved collections. This allows us to prove that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker et al. (2021) [1]. As a consequence, it follows that many algorithmic problems can be solved in polynomial time for this class, and that even-hole-freeness is testable in the bounded degree graph model of property testing. In fact we prove our results for a larger class of graphs, namely the class of C4-free odd-signable graphs with bounded degree.

KW - Even-hole-free graphs

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85132576893&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132576893&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2022.05.009

DO - 10.1016/j.jctb.2022.05.009

M3 - Article

AN - SCOPUS:85132576893

SN - 0095-8956

VL - 157

SP - 144

EP - 175

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -