Key points are not available for this paper at this time.
When T is a tree decomposition of a graph G, we write (T) for the maximum size of an induced matching in G all of whose edges intersect one bag of T. The induced matching treewidth of a graph G is the minimum value of (T) over all tree decompositions T of~G. Classes of graphs with bounded induced matching treewidth admit polynomial-time algorithms for a number of problems, including INDEPENDENT SET, k-COLORING, ODD CYCLE TRANSVERSAL, and FEEDBACK VERTEX SET. In this paper, we focus on structural 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 -bounded. Our results confirm two conjectures from a recent manuscript of Lima et al. arXiv 2024.
Abrishami et al. (Tue,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: