***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Isolde Adler (Leeds)

Thursday 24th September, 15:00 via Zoom.

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

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.


		----------------------------------

Next week: Colin Defant and Noah Kravitz 

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)