Beziehung zwischen Baumbreite und Cliquenzahl

Gibt es nette Graphklassen, für die die durch eine Funktion der Cliquennummer , dh ? $tw(G)$ $\omega(G)$ $tw(G)\leq f(\omega(G))$

Zum Beispiel ist es eine klassische Tatsache, dass wir für jeden Akkordgraphen . Klassen, die sich auf Akkordgraphen beziehen, könnten also gute Kandidaten sein. $G$ $tw(G)=\omega(G)-1$

graph-theory treewidth Florent Foucaud
quelle

tw für Akkordgraphen.

(G) = ω (G) - 1

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

Yixin Cao

Da die Baumbreite unter Aufnahme von Teilgraphen geschlossen ist, muss die Baumbreite von G mindestens die Baumbreite von , die ist , wenn ein Graph als Teilgraphen hat .

G

$G$

K_{n}

$K_n$

K_{n}

$K_n$

n - 1

$n-1$

Mateus de Oliveira Oliveira

@ Matheus Ich denke die Frage ist umgekehrt. Er bittet um eine Obergrenze und Ihr Beispiel gibt eine Untergrenze an.

Vinicius dos Santos

@ Bart Jansen: Split-Graphen sind akkordisch.

Florent Foucaud

@FlorentFoucaud, Sie sollten erwägen, Ihre Bearbeitung in eine Antwort umzuwandeln.

Vinicius dos Santos

Antworten:

Auf dieser Seite wird ein Satz erwähnt, der solche Klassen bereitstellt:

Satz (Scheffler [1]) Wenn der Schnittgraph verbundener Teilgraphen eines anderen Graphen , dann ist . $G$ $H$ $tw(G)\leq tw(H)\omega(G)-1$

Dies verallgemeinert die Grenze für Akkordgraphen (für die ein Baum ist) und gilt auch für Kreisbogengraphen (dann ist ein Zyklus). Ich weiß nicht, ob andere "Standard" -Klassen von diesem Theorem erfasst werden. $H$ $H$

[1] P. Scheffler, Welche Graphen haben die Baumbreite begrenzt? Rostocker Math. Kolloq. 41 (1990) 31-38.

Florent Foucaud
quelle

"unzugänglich"? Du meinst, Papier ist nicht online?

vzn

Eigentlich dachte ich zuerst, dies sei ein Konferenzgespräch, aber offensichtlich hat dies einige Seitenzahlen. Es gibt eine Website für das Journal ( math.uni-rostock.de/math/pub/romako ). Ich habe gefragt, ob es möglich ist, eine Kopie zu erhalten.

Florent Foucaud

Ich denke, es ist auch nicht schwer, es selbst zu beweisen. Möglicherweise ist es schneller als eine Kopie des Papiers zu erhalten :)

Saeed

@Saeed Möglicherweise, aber ich hoffe besonders, in diesem Artikel eine Diskussion über das Thema zu finden!

Florent Foucaud

Satz (6.4 in [1]): Wenn keine Pfanne und kein gerades Loch als induzierten Teilgraphen hat, dann . $G$ $tw(G)\leq 3\omega(G)/2-2$

Satz (5.4 in [2]): Wenn ungerade signierbar ist, keinen Clique-Cutset hat und weder eine Kappe noch einen 4-Zyklus als induzierten Subgraphen hat, dann . (Dies gilt insbesondere dann, wenn keinen Clique-Cutset und keine Kappe und kein gleichmäßiges Loch als induzierten Subgraphen hat.) $G$ $tw(G)\leq 6\omega(G)-1$ $G$

[1] K. Cameron, S. Chaplick, CT Hoang. Zur Struktur von (Pan, Even Hole) -freien Grafiken, 2015. https://arxiv.org/abs/1508.03062

[2] K. Cameron, MVG da Silva, S. Huang, K. Vušković. Struktur und Algorithmen für (Kappe, gerade Loch) -freie Diagramme, 2016. https://arxiv.org/abs/1611.08066

Florent Foucaud
quelle