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 (tw,\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 (tw,\omega)-bounded. Our results  imply that the class of 1-perfectly orientable graphs is (tw,\omega)-bounded, answering a question of Bresar, Hartinger, Kos  and Milanic from 2018. We also reveal some further algorithmic implications of (tw,\omega)-boundedness related to list k-coloring and clique problems  .
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 closed under taking induced subgraphs in which this condition is also sufficient, which we call (tw,\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 (tw,\omega)-bounded. Our results yield an infinite family of \chi-bounded induced-minor-closed graph classes and imply that the class of 1-perfectly orientable graphs is (tw,\omega)-bounded, leading to linear-time algorithms for k-coloring 1-perfectly orientable graphs for every fixed k. This answers a question of Bresar, Hartinger, Kos , and Milanic from 2018, and one of Beisegel, Chudnovsky, Gurvich, Milani\v{c We also reveal some further algorithmic implications of (tw,\omega)-boundedness related to list k-coloring and clique problems . In addition, we propose a question about the complexity of the Maximum Weight Independent Set problem in (tw,\omega)-bounded graph classes and prove that the problem is polynomial-time solvable in every class of graphs excluding a fixed star as an induced minor .
A
closed under taking induced subgraphs
A
yield an infinite family of \chi-bounded induced-minor-closed graph classes and
R
answering
leading to linear-time algorithms for k-coloring 1-perfectly orientable graphs for every fixed k. This answers
A
,
R
2018.
2018, and one of Beisegel, Chudnovsky, Gurvich, Milani\v{c
A
. In addition, we propose a question about the complexity of the Maximum Weight Independent Set problem in (tw,\omega)-bounded graph classes and prove that the problem is polynomial-time solvable in every class of graphs excluding a fixed star as an induced minor