# Relation between tree-width and clique number

Are there any nice graph classes for which the tree-width $tw(G)$ is upper-bounded by a function of the clique number $\omega(G)$, i.e. $tw(G)\leq f(\omega(G))$?

For example, it is a classic fact that for any chordal graph $G$, we have $tw(G)=\omega(G)-1$. So, classes related to chordal graphs could be good candidates.

• tw$(G) = \omega(G) - 1$ for chordal graphs. May 9 '14 at 18:27
• since treewidth is closed under taking subgraphs, if a graph $G$ has $K_n$ as subgraph then the treewidth of G must be at least the treewidth of $K_n$, which is $n-1$. May 9 '14 at 18:33
• @Matheus I think the question is the other way around. He is asking for an upper bound and your example gives a lower bound. May 9 '14 at 22:58
• @Bart Jansen: split graphs are chordal. May 10 '14 at 16:11
• @FlorentFoucaud, you should consider turning your edit into an answer. May 11 '14 at 1:23

Theorem (Scheffler [1]) If $G$ is the intersection graph of connected subgraphs of another graph $H$, then $tw(G)\leq tw(H)\omega(G)-1$.

This generalizes the bound for chordal graphs (for which $H$ is a tree) and also applies to circular-arc graphs (then $H$ is a cycle). I do not know if other "standard" classes are captured by this theorem.

[1] P. Scheffler, What graphs have bounded tree-width? Rostocker Math. Kolloq. 41 (1990) 31-38.

• "inaccessable"? you mean paper is not online?
– vzn
May 11 '14 at 23:11
• Actually at first I thought this is a conference talk but obviously this has some page numbers. There is a website for the journal (math.uni-rostock.de/math/pub/romako), I've asked whether it is possible to obtain a copy. May 12 '14 at 8:12
• I think it's also not hard to prove it yourself. Possibly it's faster than receiving a copy of paper :) May 12 '14 at 16:47
• @Saeed Possibly, but I'm especially hoping to find some discussion about the topic in that paper! May 12 '14 at 18:50

Theorem (6.4 in [1]): If $G$ has no pan and no even hole as an induced subgraph, then $tw(G)\leq 3\omega(G)/2-2$.

Theorem (5.4 in [2]): If $G$ is odd-signable, has no clique cutset and has no cap nor any 4-cycle as an induced subgraph, then $tw(G)\leq 6\omega(G)-1$. (In particular, this holds if $G$ has no clique cutset and has no cap and no even hole as an induced subgraph.)

[1] K. Cameron, S. Chaplick, C. T. Hoang. On the structure of (pan, even hole)-free graphs, 2015. https://arxiv.org/abs/1508.03062

[2] K. Cameron, M. V. G. da Silva, S. Huang, K. Vušković. Structure and algorithms for (cap, even hole)-free graphs, 2016. https://arxiv.org/abs/1611.08066

This recent paper studies the question in more depth:

Clément Dallard, Martin Milanič, Kenny Štorgel. Treewidth versus clique number in graph classes with a forbidden structure. https://arxiv.org/abs/2006.06067