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

<p><b>Theorem (5.4 in [2]):</b> 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.)</p>

<p>[1] K. Cameron, S. Chaplick, C. T. Hoang. On the structure of (pan, even hole)-free graphs, 2015. <a href="https://arxiv.org/abs/1508.03062" rel="nofollow noreferrer">https://arxiv.org/abs/1508.03062</a></p>

<p>[2] K. Cameron, M. V. G. da Silva, S. Huang, K. Vušković. Structure and algorithms for (cap, even hole)-free graphs, 2016. <a href="https://arxiv.org/abs/1611.08066" rel="nofollow noreferrer">https://arxiv.org/abs/1611.08066</a></p>

CC BY-SA 3.0
2016-11-08T08:50:36.910Z
2016-11-30T16:59:59.677Z
2016-11-30T16:59:59.677Z
Florent Foucaud
<p>This recent paper studies the question in more depth:</p>

<p>Clément Dallard, Martin Milanič, Kenny Štorgel. Treewidth versus clique number in graph classes with a forbidden structure. <a href="https://arxiv.org/abs/2006.06067" rel="nofollow noreferrer">https://arxiv.org/abs/2006.06067</a></p>

CC BY-SA 4.0
2020-06-15T11:52:26.120Z
2020-06-15T11:52:26.120Z
Florent Foucaud
<p>On <a href="http://www.eprisner.de/Journey/Opti.html" rel="nofollow">this page</a> a theorem is mentioned that provides such classes:</p>

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

<p>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.</p>



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

CC BY-SA 3.0
2014-05-11T23:11:40.263Z
"inaccessable"? you mean paper is not online?
vzn
CC BY-SA 3.0
2014-05-12T08:12:15.217Z
Actually at first I thought this is a conference talk but obviously this has some page numbers. There is a website for the journal (http://www.math.uni-rostock.de/math/pub/romako/), I've asked whether it is possible to obtain a copy.
Florent Foucaud
CC BY-SA 3.0
2014-05-12T16:47:46.267Z
I think it's also not hard to prove it yourself. Possibly it's faster than receiving a copy of paper :)
Saeed
CC BY-SA 3.0
2014-05-12T18:50:21.187Z
@Saeed Possibly, but I'm especially hoping to find some discussion about the topic in that paper!
Florent Foucaud
CC BY-SA 3.0
2014-05-11T17:04:35.957Z
2014-05-12T08:12:36.610Z
2014-05-12T08:12:36.610Z
Florent Foucaud
<p>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))$?</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-09T18:27:18.127Z
tw$(G) = \omega(G) - 1$ for chordal graphs.
Yixin Cao
CC BY-SA 3.0
2014-05-09T18:33:44.180Z
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$.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2014-05-09T22:58:05.120Z
@Matheus I think the question is the other way around. He is asking for an upper bound and your example gives a lower bound.
Vinicius dos Santos
CC BY-SA 3.0
2014-05-10T14:41:07.773Z
$tw(G) \leq  \omega(G)$ for split graphs, i.e., graphs whose vertex set can be partitioned into an independent set and a clique. (Take one bag containing the clique, then for every vertex v in the independent set make a new bag containing the clique with v, and attach the bag in the tree decomposition to the bag containing just the clique.) For all hereditary graphs containing all complete bipartite graphs or all grids, there is no such bound, ruling out a lot of natural classes.
Bart Jansen
CC BY-SA 3.0
2014-05-10T16:11:12.633Z
@Yixin Cao: edited.
Florent Foucaud
CC BY-SA 3.0
2014-05-10T16:11:29.787Z
@Bart Jansen: split graphs are chordal.
Florent Foucaud
CC BY-SA 3.0
2014-05-11T01:23:58.913Z
@FlorentFoucaud, you should consider turning your edit into an answer.
Vinicius dos Santos
CC BY-SA 3.0
2014-05-11T17:09:27.623Z
@Vinicius dos Santos: OK, done.
Florent Foucaud
CC BY-SA 3.0
2014-05-12T19:29:46.870Z
There has been a lot of study recently on $\chi$-bounded graph classes, which are defined by taking your question and replacing treewidth with chromatic number.  Since treewidth gives you an upper bound for $\chi$, every $\chi$-bounded class of graphs satisfies your constraint.

See http://arxiv.org/abs/1302.1145 for an example of recent research.
Andrew D. King
CC BY-SA 3.0
2014-05-12T20:53:12.507Z
@Andrew D. King: I think that gives me the wrong way: bipartite graphs are obviously $\chi$-bounded but I can't upper-bound the tree-width by the clique number (see e.g. grids, as pointed out by Bart)
Florent Foucaud
CC BY-SA 3.0
2014-06-04T22:56:32.100Z
Sorry of course you're right; I'm thinking backwards.
Andrew D. King
<graph-theory><treewidth>
Relation between tree-width and clique number
Florent Foucaud
# Relation between tree-width and clique number

(Asked by: username_0 on 2014-05-09)

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.

**Tags:** graph-theory, treewidth

> **Comments:**
> **username_1**: tw$(G) = \omega(G) - 1$ for chordal graphs.  
> **username_2**: 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$.  
> **username_3**: @Matheus I think the question is the other way around. He is asking for an upper bound and your example gives a lower bound.  
> **username_4**: $tw(G) \leq  \omega(G)$ for split graphs, i.e., graphs whose vertex set can be partitioned into an independent set and a clique. (Take one bag containing the clique, then for every vertex v in the independent set make a new bag containing the clique with v, and attach the bag in the tree decomposition to the bag containing just the clique.) For all hereditary graphs containing all complete bipartite graphs or all grids, there is no such bound, ruling out a lot of natural classes.  
> **username_0**: @username_1: edited.  
> **username_0**: @username_4: split graphs are chordal.  
> **username_3**: @FlorentFoucaud, you should consider turning your edit into an answer.  
> **username_0**: @username_3: OK, done.  
> **username_5**: There has been a lot of study recently on $\chi$-bounded graph classes, which are defined by taking your question and replacing treewidth with chromatic number.  Since treewidth gives you an upper bound for $\chi$, every $\chi$-bounded class of graphs satisfies your constraint.  See http://arxiv.org/abs/1302.1145 for an example of recent research.  
> **username_0**: @username_5: I think that gives me the wrong way: bipartite graphs are obviously $\chi$-bounded but I can't upper-bound the tree-width by the clique number (see e.g. grids, as pointed out by Bart)  
> **username_5**: Sorry of course you're right; I'm thinking backwards.  

---

## 3 answers

### Answer by username_0 on 2014-05-11. Score: 10 | Accepted answer

On [this page](http://www.eprisner.de/Journey/Opti.html) a theorem is mentioned that provides such classes:

**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.

> **Comments:**
> **username_6**: "inaccessable"? you mean paper is not online?  
> **username_0**: Actually at first I thought this is a conference talk but obviously this has some page numbers. There is a website for the journal (http://www.math.uni-rostock.de/math/pub/romako/), I've asked whether it is possible to obtain a copy.  
> **username_7**: I think it's also not hard to prove it yourself. Possibly it's faster than receiving a copy of paper :)  
> **username_0**: @username_7 Possibly, but I'm especially hoping to find some discussion about the topic in that paper!  

---

### Answer by username_0 on 2016-11-08. Score: 6

**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>


---

### Answer by username_0 on 2020-06-15. Score: 2

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>


---

