Treewidth versus clique number in graph classes with a forbidden structure

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call (treewidth, omega)-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and k-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is (treewidth, omega)-bounded. Our results imply that the class of 1-perfectly orientable graphs is (treewidth, omega)-bounded, answering a question of Brešar, Hartinger, Kos, and Milanič from 2018. We also reveal some further algorithmic implications of (treewidth,omega)-boundedness related to list k-coloring and clique problems. This is joint work with Clément Dallard and Kenny Štorgel.