Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth

We prove that for every integer $t\ge 1$ there exists an integer $c_t\ge 1$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\log n$. This resolves a conjecture of Sintiari and Trotignon, who also proved that the logarithmic bound is asymptotically best possible. It follows that several $\mathsf{\text{NP}}$-hard problems such as $\text{textsc}StableSet$, $\text{textsc}VertexCover$, $\text{textsc}DominatingSet$ and $\text{textsc}Coloring$ admit polynomial-time algorithms on this class of graphs. As a consequence, for every positive integer $r$, $r$-{\sc 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 $\mathsf{\text{NP}}$-hard problems while restricted to the class of all even-hole-free graphs.