On treewidth and maximum cliques
Chudnovsky, Maria1; Trotignon, Nicolas2
1 Princeton University, Princeton, NJ 08544, USA
2 CNRS, ENS de Lyon, Université Lyon 1, LIP UMR 5668, 69342 Lyon Cedex 07, France.
Innovations in Graph Theory, Volume 2 (2025), pp. 223-243.

We construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique number, the construction can be adjusted to make the dependence grow arbitrarily. Some of these classes provide counter-examples to several conjectures. In particular, the construction includes hereditary classes of graphs whose treewidth is bounded by a function of the clique number while the tree-independence number is unbounded, thus disproving a conjecture of Dallard, Milanič and Štorgel [Treewidth versus clique number. II. Tree-independence number. Journal of Combinatorial Theory, Series B, 164:404–442, 2024]. The construction can be further adjusted to provide, for any fixed integer $c$, graphs of arbitrarily large treewidth that contain no $K_c$-free graphs of high treewidth, thus disproving a conjecture of Hajebi [Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth, arXiv:2401.01299, 2024].

Received:
Accepted:
Published online:
DOI: 10.5802/igt.11
Classification: 05C75, 05C85, 05C69
Keywords: treewidth, tree-independence number, clique

Chudnovsky, Maria 1; Trotignon, Nicolas 2

1 Princeton University, Princeton, NJ 08544, USA
2 CNRS, ENS de Lyon, Université Lyon 1, LIP UMR 5668, 69342 Lyon Cedex 07, France.
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2025__2__223_0,
     author = {Chudnovsky, Maria and Trotignon, Nicolas},
     title = {On treewidth and maximum cliques},
     journal = {Innovations in Graph Theory},
     pages = {223--243},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     year = {2025},
     doi = {10.5802/igt.11},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.11/}
}
TY  - JOUR
AU  - Chudnovsky, Maria
AU  - Trotignon, Nicolas
TI  - On treewidth and maximum cliques
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 223
EP  - 243
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.11/
DO  - 10.5802/igt.11
LA  - en
ID  - IGT_2025__2__223_0
ER  - 
%0 Journal Article
%A Chudnovsky, Maria
%A Trotignon, Nicolas
%T On treewidth and maximum cliques
%J Innovations in Graph Theory
%D 2025
%P 223-243
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.11/
%R 10.5802/igt.11
%G en
%F IGT_2025__2__223_0
Chudnovsky, Maria; Trotignon, Nicolas. On treewidth and maximum cliques. Innovations in Graph Theory, Volume 2 (2025), pp. 223-243. doi : 10.5802/igt.11. https://igt.centre-mersenne.org/articles/10.5802/igt.11/

[1] Abrishami, Tara; Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie; Vušković, Kristina Tree independence number I. (even hole, diamond, pyramid)-free graphs, J. Graph Theory, Volume 106 (2024) no. 4, pp. 923-943 | DOI | Zbl

[2] Abrishami, Tara; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie Induced Subgraphs and Tree Decompositions III, Adv. Comb., Volume 2022 (2022), Paper no. 6, 29 pages | DOI | Zbl

[3] Corneil, Derek G.; Rotics, Udi On the Relationship Between Clique-Width and Treewidth, SIAM J. Comput., Volume 34 (2005) no. 4, pp. 825-847 | DOI | MR | Zbl

[4] Dallard, Clément; Milanič, Martin; Štorgel, Kenny Treewidth versus clique number. I. Graph classes with a forbidden structure, SIAM J. Discrete Math., Volume 35 (2021) no. 4, pp. 2618-2646 | DOI | MR | Zbl

[5] Dallard, Clément; Milanič, Martin; Štorgel, Kenny Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, Volume 164 (2024), pp. 404-442 | DOI | MR | Zbl

[6] Dallard, Clément; Milanič, Martin; Štorgel, Kenny Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure, J. Comb. Theory, Ser. B, Volume 167 (2024), pp. 338-391 | arXiv | DOI | MR | Zbl

[7] Dirac, Gabriel Andrew On rigid circuit graphs, Abh. Math. Semin. Univ. Hamb., Volume 25 (1961), pp. 71-76 | DOI | MR | Zbl

[8] Dvořák, Zdenek; Norin, Sergey Treewidth of graphs with balanced separations, J. Comb. Theory, Ser. B, Volume 137 (2019), pp. 137-144 | DOI | MR | Zbl

[9] Hajebi, Sepehr Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth (2024) | arXiv | Zbl

[10] Robertson, Neil; Seymour, Paul Graph minors. V. Excluding a planar graph, J. Comb. Theory, Ser. B, Volume 41 (1986) no. 1, pp. 92-114 | DOI | MR | Zbl

[11] Rose, Donald J. Triangulated graphs and the elimination process, J. Math. Anal. Appl., Volume 32 (1970) no. 3, p. 597--609 | DOI | MR | Zbl

[12] Sintiari, Ni Luh Dewi; Trotignon, Nicolas (Theta, triangle)-free and (even hole, K 4 )-free graphs - Part 1: Layered wheels, J. Graph Theory, Volume 97 (2021) no. 4, pp. 475-509 | DOI | MR | Zbl

[13] Yolov, Nikola Minor-matching hypertree width, Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2018, pp. 219-233 | DOI | MR | Zbl

Cited by Sources: