|国家预印本平台
首页|Excluding a clique or a biclique in graphs of bounded induced matching treewidth

Excluding a clique or a biclique in graphs of bounded induced matching treewidth

Excluding a clique or a biclique in graphs of bounded induced matching treewidth

来源:Arxiv_logoArxiv
英文摘要

For a tree decomposition $\mathcal{T}$ of a graph $G$, let $\mu(\mathcal{T})$ denote the maximum size of an induced matching in $G$ with the property that some bag of $\mathcal{T}$ contains at least one endpoint of every edge of the matching. The induced matching treewidth of a graph $G$ is the minimum value of $\mu(\mathcal{T})$ over all tree decompositions $\mathcal{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 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 $\chi$-bounded. The two results confirm two conjectures due to Lima et al. [ESA 2024].

Martin Milani?、Pawe? Rz??ewski、Bartosz Walczak、Tara Abrishami、Jadwiga Czy?ewska、Marcin Bria¨?ski、Rose McCarty

计算技术、计算机技术

Martin Milani?,Pawe? Rz??ewski,Bartosz Walczak,Tara Abrishami,Jadwiga Czy?ewska,Marcin Bria¨?ski,Rose McCarty.Excluding a clique or a biclique in graphs of bounded induced matching treewidth[EB/OL].(2024-05-07)[2025-08-02].https://arxiv.org/abs/2405.04617.点此复制

评论