13
$\begingroup$

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.

$\endgroup$
11
  • 9
    $\begingroup$ tw$(G) = \omega(G) - 1$ for chordal graphs. $\endgroup$
    – Yixin Cao
    Commented May 9, 2014 at 18:27
  • $\begingroup$ 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$. $\endgroup$ Commented May 9, 2014 at 18:33
  • 1
    $\begingroup$ @Matheus I think the question is the other way around. He is asking for an upper bound and your example gives a lower bound. $\endgroup$ Commented May 9, 2014 at 22:58
  • 1
    $\begingroup$ @Bart Jansen: split graphs are chordal. $\endgroup$ Commented May 10, 2014 at 16:11
  • 1
    $\begingroup$ @FlorentFoucaud, you should consider turning your edit into an answer. $\endgroup$ Commented May 11, 2014 at 1:23

3 Answers 3

10
$\begingroup$

On this page 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.

$\endgroup$
4
  • $\begingroup$ "inaccessable"? you mean paper is not online? $\endgroup$
    – vzn
    Commented May 11, 2014 at 23:11
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 12, 2014 at 8:12
  • $\begingroup$ I think it's also not hard to prove it yourself. Possibly it's faster than receiving a copy of paper :) $\endgroup$
    – Saeed
    Commented May 12, 2014 at 16:47
  • 1
    $\begingroup$ @Saeed Possibly, but I'm especially hoping to find some discussion about the topic in that paper! $\endgroup$ Commented May 12, 2014 at 18:50
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.