What type of study is this?

This is a Experimental Study study.

October 1, 2025Open Access

On treewidth and maximum cliques

Key Points

The construction reveals instances where treewidth is bounded by the clique number, yet dependencies can be manipulated.
Counter-examples are presented, disproving conjectures related to tree-independence and hereditary classes of graphs.
Arbitrarily large treewidth graphs are constructed, which lack specific high treewidth structures, challenging established theories.
These findings provide insights into the complexities of graph properties and their interrelations.

Abstract

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.

On treewidth and maximum cliques

Key Points

Abstract

Cite This Study

Also Consider

Also Consider