Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph that satisfies some property definable in CMSO₂ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for P₆-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to P₇-free graphs of bounded clique number.

Abstract. For a tree decomposition [Formula: see text] of a graph [Formula: see text], let [Formula: see text] denote the maximum size of an induced matching in [Formula: see text] with the property that some bag of [Formula: see text] contains at least one endpoint of every edge of the matching. The induced matching treewidth of a graph [Formula: see text] is the minimum value of [Formula: see text] over all tree decompositions [Formula: see text] of [Formula: see text]. Classes of graphs with bounded induced matching treewidth admit polynomial-time algorithms for a number of problems, including Independent Set, [Formula: see text]-Coloring, Odd Cycle Transversal, and Feedback Vertex Set. In this paper, we focus on combinatorial properties of such classes. First, we show that graphs with bounded induced matching treewidth that exclude a fixed biclique as an induced subgraph have bounded tree-independence number, which is another well-studied parameter defined in terms of tree decompositions. This sufficient condition about excluding a biclique is also necessary, as bicliques have unbounded tree-independence number. Second, we show that graphs with bounded induced matching treewidth that exclude a fixed clique have bounded chromatic number, that is, classes of graphs with bounded induced matching treewidth are [Formula: see text]-bounded. The two results confirm two conjectures due to Lima et al. [32 nd Annual European Symposium on Algorithms (ESA 2024), LIPIcs 308, pp. 85:1–85:17].