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.

Improve this question
$\endgroup$
11
  • 9
    $\begingroup$ tw$(G) = \omega(G) - 1$ for chordal graphs. $\endgroup$
    – Yixin Cao
    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$
    – Mateus de Oliveira Oliveira
    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$
    – Vinicius dos Santos
    May 9, 2014 at 22:58
  • 1
    $\begingroup$ @Bart Jansen: split graphs are chordal. $\endgroup$
    – Florent Foucaud
    May 10, 2014 at 16:11
  • 1
    $\begingroup$ @FlorentFoucaud, you should consider turning your edit into an answer. $\endgroup$
    – Vinicius dos Santos
    May 11, 2014 at 1:23

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "inaccessable"? you mean paper is not online? $\endgroup$
    – vzn
    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$
    – Florent Foucaud
    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
    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$
    – Florent Foucaud
    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

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

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

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