DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.31

On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs

Authors: Alex Koutsoutis, Kilian Krause, Chun-Hung Liu, Mirza Redzic, and Torsten Ueckerdt

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

We investigate the relationship between graph parameters, which measure the complexity of the tree decompositions of a given graph. The treewidth 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 tree-α(G) and the tree-chromatic number tree-χ(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 tw(G)+1 ≤ tree-α(G) ⋅ tree-χ(G). We provide a negative answer for this question in a strong form: for every function f: {ℕ} → {ℕ}, there exists a graph G such that tw(G) > tree-α(G) ⋅ f(tree-χ(G)). On the other hand, we complement this result with an upper bound, by showing that tw(G)+1 ≤ tree-α(G)² ⋅ tree-χ(G) for every graph G.

Cite as

Alex Koutsoutis, Kilian Krause, Chun-Hung Liu, Mirza Redzic, and Torsten Ueckerdt. On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 31:1-31:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koutsoutis_et_al:LIPIcs.WG.2026.31,
  author =	{Koutsoutis, Alex and Krause, Kilian and Liu, Chun-Hung and Redzic, Mirza and Ueckerdt, Torsten},
  title =	{{On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{31:1--31:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.31},
  URN =		{urn:nbn:de:0030-drops-261978},
  doi =		{10.4230/LIPIcs.WG.2026.31},
  annote =	{Keywords: Tree-independence number, Tree-chromatic number, Treewidth}
}

Search Results

Documents authored by Koutsoutis, Alex

On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message