Treewidth versus clique number in graph classes with a forbidden structure
share
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,ω)-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,ω)-bounded. Our results imply that the class of 1-perfectly orientable graphs is (tw,ω)-bounded, answering a question of Brešar, Hartinger, Kos and Milanič from 2018. We also reveal some further algorithmic implications of (tw,ω)-boundedness related to list k-coloring and clique problems.
READ FULL TEXT