10
$\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$
  • 9
    $\begingroup$ tw$(G) = \omega(G) - 1$ for chordal graphs. $\endgroup$ – Yixin Cao May 9 '14 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 '14 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 '14 at 22:58
  • 1
    $\begingroup$ @Bart Jansen: split graphs are chordal. $\endgroup$ – Florent Foucaud May 10 '14 at 16:11
  • 1
    $\begingroup$ @FlorentFoucaud, you should consider turning your edit into an answer. $\endgroup$ – Vinicius dos Santos May 11 '14 at 1:23
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$
  • $\begingroup$ "inaccessable"? you mean paper is not online? $\endgroup$ – vzn May 11 '14 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 '14 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 '14 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 '14 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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