Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913560388435968 |
|---|---|
| author | Abrishami, Tara Briański, Marcin Czyżewska, Jadwiga McCarty, Rose Milanič, Martin Rzążewski, Paweł Walczak, Bartosz |
| author_facet | Abrishami, Tara Briański, Marcin Czyżewska, Jadwiga McCarty, Rose Milanič, Martin Rzążewski, Paweł Walczak, Bartosz |
| contents | For a tree decomposition $\mathcal{T}$ of a graph $G$, let $μ(\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 $μ(\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 $χ$-bounded. The two results confirm two conjectures due to Lima et al. [ESA 2024]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04617 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Excluding a clique or a biclique in graphs of bounded induced matching treewidth Abrishami, Tara Briański, Marcin Czyżewska, Jadwiga McCarty, Rose Milanič, Martin Rzążewski, Paweł Walczak, Bartosz Combinatorics For a tree decomposition $\mathcal{T}$ of a graph $G$, let $μ(\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 $μ(\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 $χ$-bounded. The two results confirm two conjectures due to Lima et al. [ESA 2024]. |
| title | Excluding a clique or a biclique in graphs of bounded induced matching treewidth |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.04617 |