Even-hole-free graphs with bounded degree have bounded treewidth

The class of even-hole-free graphs (i.e. graphs that do not contain a chordless cycle on an even number of vertices) has been studied since the 1990's, initially motivated by their structural similarity to perfect graphs. It is known for example that they can be decomposed by star cutsets and 2-joins into graphs that are line graphs of a tree plus at most two vertices, which has led to, for example, their polynomial time recognition. Nevertheless, the complexity of a number of classical computational problems remain open for this class, such as the coloring and stable set problems.

In this talk we show that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker, Adler, Kim, Sintiari and Trotignon. This implies that many algorithmic problems can be solved in polynomial time for this class. Furthermore, it shows that even-hole-freeness is testable in the bounded degree graph model of property testing.

Treewidth is a parameter that emerged out of 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 for even-hole-free graphs, perfect graphs and others. They do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by these decomposition theorems are far from being noncrossing. In the case of even-hole-free graphs of bounded degree we show how these cutsets can be partitioned into a bounded number of well-behaved collections, which allows us to bound the treewidth of such graphs.