Theoretical study demonstrates arbitrary treewidth growth relative to clique number in layered wheel variants, highlighting counterexamples to structural graph conjectures.
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 dependance 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{c} and {S}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 Kc-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].
No takes yet. Share an insight, caveat, or question.
Chudnovsky et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: