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.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
The slides of the talk are available HERE.
If you missed it, you can watch the lecture via the following link:
Passcode: kKx7cM?n