In recent years, even-hole-free graphs were the object of much attention, however, many questions remain unanswered, such as the existence of a polynomial time algorithm for colouring even-hole-free graphs, or for finding a maximum stable set. The class of 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 show the class of even-hole-free graphs excluding a minor has bounded tree-width (1). This implies that planar even-hole-free graphs have bounded tree-width [da Silva and Linhares Sales, 2010]. To prove this, we provide an "induced grid theorem" for minor-free graphs. We conjecture that for every d, the class of even-hole-free graphs of degree at most d has bounded tree-width, and we obtain partial results. * The class of even-hole-free graphs of degree at most 3 has bounded tree-width. * The class of (even-hole, pyramid)-free graphs of degree at most 4 has bounded tree-width. In the meantime, our conjecture has been proven [Abrishami, Chudnovsky and Vuskovic, 2020]. Our second source of motivation for studying the tree-width of even-hole-free graphs stems from the area of property testing, namely, from the question whether even-hole-freeness is testable in the bounded degree model. Indeed, since our conjecture holds, this question is now answered. In this talk I will explain the proof of (1), and give some background on property testing and testability of even-hole-freeness.

This is joint work with Pierre Aboulker, Frederik Harwath, Eunjung Kim, Noleen Köhler, Ni Luh Dewi Sintiari and Nicolas Trotignon.