Relation entre la largeur de l'arbre et le nombre de cliques

Existe-t-il des classes de graphes agréables pour lesquelles la largeur d'arbre est limitée par une fonction du nombre de cliques , c'est-à-dire ? $tw(G)$ $\omega(G)$ $tw(G)\leq f(\omega(G))$

Par exemple, c'est un fait classique que pour tout graphe d'accord , nous avons . Ainsi, les classes liées aux graphes d'accords pourraient être de bons candidats. $G$ $tw(G)=\omega(G)-1$

graph-theory treewidth Florent Foucaud
la source

pour les graphes d'accord.

(G) = ω (G) - 1

$(G) = \omega(G) - 1$

Yixin Cao

puisque la largeur d'arbre est fermée en prenant des sous-graphes, si un graphe

comme sous-graphe, alors la largeur d'arbre de G doit être au moins la largeur d'arbre de

, qui est

G

$G$

K_{n}

$K_n$

K_{n}

$K_n$

n - 1

$n-1$

Mateus de Oliveira Oliveira

@Matheus Je pense que la question est l'inverse. Il demande une borne supérieure et votre exemple donne une borne inférieure.

Vinicius dos Santos

@ Bart Jansen: les graphiques fractionnés sont en accords.

Florent Foucaud

@FlorentFoucaud, vous devriez envisager de transformer votre modification en réponse.

Vinicius dos Santos

Réponses:

Sur cette page, un théorème est mentionné qui fournit de telles classes:

$G$ $H$ $tw(G)\leq tw(H)\omega(G)-1$

$H$ $H$

[1] P. Scheffler, Quels graphiques ont une largeur d'arbre bornée? Rostocker Math. Kolloq. 41 (1990) 31-38.

Florent Foucaud
la source

"inaccessible"? vous voulez dire que le papier n'est pas en ligne?

vzn

En fait, au début, je pensais que c'était une conférence, mais il y a évidemment des numéros de page. Il existe un site Web pour la revue ( math.uni-rostock.de/math/pub/romako ), j'ai demandé s'il était possible d'en obtenir une copie.

Florent Foucaud

Je pense qu'il n'est pas difficile non plus de le prouver vous-même. C'est peut-être plus rapide que de recevoir une copie papier :)

Saeed

@Saeed Peut-être, mais j'espère surtout trouver une discussion sur le sujet dans cet article!

Florent Foucaud

$G$ $tw(G)\leq 3\omega(G)/2-2$

$G$ $tw(G)\leq 6\omega(G)-1$ $G$

[1] K. Cameron, S. Chaplick, CT Hoang. Sur la structure des graphiques libres (pan, trou pair), 2015. https://arxiv.org/abs/1508.03062

[2] K. Cameron, MVG da Silva, S. Huang, K. Vušković. Structure et algorithmes pour les graphiques sans (capuchon, trou égal), 2016. https://arxiv.org/abs/1611.08066

Florent Foucaud
la source