On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917208631803904 |
|---|---|
| author | Koutsoutis, Alex Krause, Kilian Liu, Chun-Hung Redzic, Mirza Ueckerdt, Torsten |
| author_facet | Koutsoutis, Alex Krause, Kilian Liu, Chun-Hung Redzic, Mirza Ueckerdt, Torsten |
| contents | We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth ${\rm tw}(G)$ of a graph $G$ measures the largest number of vertices required in a bag of every tree decomposition of $G$. Similarly, the tree-independence number ${\rm tree\textnormal{-}}α(G)$ and the tree-chromatic number ${\rm tree\textnormal{-}}χ(G)$ measure the largest independence number, respectively the largest chromatic number, required in a bag of every tree decomposition of $G$.
Recently, Dallard, Milanič, and Štorgel asked (JCTB, 2024) whether for all graphs $G$ it holds that ${\rm tw}(G)+1 \leq {\rm tree\textnormal{-}}α(G) \cdot {\rm tree\textnormal{-}}χ(G)$. We provide a negative answer for this question in a strong form: for every function $f\colon {\mathbb N} \rightarrow {\mathbb N}$, there exists a graph $G$ such that ${\rm tw}(G) > {\rm tree\textnormal{-}}α(G) \cdot f({\rm tree\textnormal{-}}χ(G))$. On the other hand, we complement this result with an upper bound, by showing that ${\rm tw}(G)+1 \leq {\rm tree\textnormal{-}}α(G)^2 \cdot {\rm tree\textnormal{-}}χ(G)$ for every graph $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19751 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs Koutsoutis, Alex Krause, Kilian Liu, Chun-Hung Redzic, Mirza Ueckerdt, Torsten Combinatorics Primary 05C75, Secondary 05C15, 05C69, 05C85 G.2.2; G.2.1; F.2.2 We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth ${\rm tw}(G)$ of a graph $G$ measures the largest number of vertices required in a bag of every tree decomposition of $G$. Similarly, the tree-independence number ${\rm tree\textnormal{-}}α(G)$ and the tree-chromatic number ${\rm tree\textnormal{-}}χ(G)$ measure the largest independence number, respectively the largest chromatic number, required in a bag of every tree decomposition of $G$. Recently, Dallard, Milanič, and Štorgel asked (JCTB, 2024) whether for all graphs $G$ it holds that ${\rm tw}(G)+1 \leq {\rm tree\textnormal{-}}α(G) \cdot {\rm tree\textnormal{-}}χ(G)$. We provide a negative answer for this question in a strong form: for every function $f\colon {\mathbb N} \rightarrow {\mathbb N}$, there exists a graph $G$ such that ${\rm tw}(G) > {\rm tree\textnormal{-}}α(G) \cdot f({\rm tree\textnormal{-}}χ(G))$. On the other hand, we complement this result with an upper bound, by showing that ${\rm tw}(G)+1 \leq {\rm tree\textnormal{-}}α(G)^2 \cdot {\rm tree\textnormal{-}}χ(G)$ for every graph $G$. |
| title | On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs |
| topic | Combinatorics Primary 05C75, Secondary 05C15, 05C69, 05C85 G.2.2; G.2.1; F.2.2 |
| url | https://arxiv.org/abs/2504.19751 |