Tree decompositions meet induced matchings
Tree decompositions meet induced matchings
Tree decompositions are an important tool in structural and algorithmic graph theory, largely due to treewidth. Several more general width parameters have been recently introduced that, unlike treewidth, can also be bounded on dense graph classes, and for which Maximum Independent Set and related problems can be solved in polynomial time when the parameter is bounded. This includes tree-independence number, introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2021, and induced matching treewidth, introduced by Yolov in 2018 (under the name minor-matching hypertreewidth). Good algorithmic properties of these parameters motivate the study of conditions for their boundedness.
The induced matching treewidth of a graph G is defined as the minimum, over all tree decompositions of G, of the maximum size of an induced matching all of whose edges intersect the same bag of the decomposition. In this talk, we will discuss structural properties of graphs with bounded induced matching treewidth. First, we will show that graphs with bounded induced matching treewidth that exclude a fixed biclique as an induced subgraph admit a tree decomposition in which no bag contains a large independent set. Second, we will show that classes of graphs with bounded induced matching treewidth and bounded clique number have bounded chromatic number. These results prove two recent conjectures of Lima, Milanič, Muršič, Okrasa, Rzążewski, and Štorgel.