Key points are not available for this paper at this time.
We prove that for every integer t 1 there exists an integer cₜ 1 such that every n-vertex even-hole-free graph with no clique of size t has treewidth at most cₜn. This resolves a conjecture of Sintiari and Trotignon, who also proved that the logarithmic bound is asymptotically best possible. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and Coloring admit polynomial-time algorithms on this class of graphs. As a consequence, for every positive integer r, r-Coloring can be solved in polynomial time on even-hole-free graphs without any assumptions on clique size. As part of the proof, we show that there is an integer d such that every even-hole-free graph has a balanced separator which is contained in the (closed) neighborhood of at most d vertices. This is of independent interest; for instance, it implies the existence of efficient approximation algorithms for certain NP-hard problems while restricted to the class of all even-hole-free graphs.
Chudnovsky et al. (Wed,) studied this question.