Wird die Clique-Breite unter Randkontraktionen beibehalten?

13

Sei eine Klasse von Graphen mit begrenzter Cliquenbreite. In jedem Graphen in einige Kanten kontrahiert (zB zufällig). Ist jetzt die Clique-Breite noch begrenzt?GGG

Für den Fall, dass es (allgemein) nicht mehr beschränkt ist, wäre ich sehr an einem Gegenbeispiel interessiert.

graph-theory co.combinatorics cliquewidth Martin Lackner
quelle

Antworten:

16

Dies könnte eine Vorab-Antwort sein: In diesem Artikel von arXiv 2007 (Aufgabe 4.9) wird als offenes Problem angegeben, ob man einen Graphen und eine Kante { x , y } ∈ E ( G ) so finden kann, dass c w ( G ) < c w ( G x , y ) , wobei G x , y der Graph G mit kontrahierter Kante { x , y } ist .G{x,y}∈E(G)cw(G)<cw(Gx,y)Gx,yG{x,y}

Mathieu Chapelle
quelle
Vielen Dank für Ihre Antwort! Das ist eine wertvolle Referenz für mich. Falls es in der Zwischenzeit noch niemand gelöst hat, wird meine Frage mehr oder weniger beantwortet :)
Martin Lackner
Ist das nicht das Gegenteil von dem, was hier gefragt wird?
Tsuyoshi Ito
Nur in dem Sinne, dass diese Frage ein Gegenbeispiel verlangt.
Martin Lackner
17

Dieses kürzlich erschienene Papier beweist schließlich, dass Randkontraktionen nicht die Eigenschaft bewahren, dass eine Reihe von Diagrammen die Clique-Breite begrenzt hat.

user13136
quelle