Cliquewidth von fast Cographs

(Ich habe diese Frage vor zwei Wochen bei MathOverflow gepostet , aber bisher ohne strenge Antwort.)

Ich habe eine Frage zu Graphenbreitenmaßen ungerichteter einfacher Graphen. Es ist bekannt, dass cographs (Graphen, die durch Operationen der disjunkten Vereinigung und Komplementierung ausgehend von isolierten Scheitelpunkten erstellt werden können) eine Cliquebreite von höchstens 2 aufweisen. Betrachte nun eine feste nicht negative ganze Zahl k und betrachte die Klasse der Graphen der Graphen so, dass es für jedes G = ( V , E ) ∈ G k eine Menge S von höchstens k Eckpunkten gibt, so dass G [ V - S ] ist ein cograph. Da die Graphklasse $\mathcal{G} _k$$G = (V,E) \in \mathcal{G} _k$$S$$G[V - S]$ kann auch als die Klasse von Graphen angesehen werden, die durch Hinzufügen von höchstens k Eckpunktenaus cographs erstellt werdenkann. Diese Klasse wurde auch cographs + k v genannt .$\mathcal{G} _k$$k$$kv$

Meine Frage ist: Was ist eine enge Grenze für die Cliquebreite von Graphen in , dh die Graphen, die durch Löschen von k Eckpunkten in ein cograph umgewandelt werden können?$\mathcal{G}_k$

Es ist bekannt, dass, wenn ein Graph aus H durch Löschen von k Eckpunkten erhalten wird, c w ( H ) ≤ 2 k ( c w ( G ) + 1 ) ist . Dies zeigt, dass, wenn ein cograph G aus einem Graphen H durch Löschen von k Eckpunkten erhalten werden kann, c w ( H ) ≤ 2 k ( 3 + 1 ) und damit die Cliquebreite eines Graphen in G$G$$H$$k$$cw(H) \leq 2^k (cw(G) + 1)$$G$$H$$k$$cw(H) \leq 2^k (3 + 1)$$\mathcal{G}_k$ist höchstens . Ich bin mir nicht sicher, ob diese exponentielle Abhängigkeit von k notwendig ist. In diesem Zusammenhang würde mich auch die maximale Verringerung der Cliquebreite durch Löschen eines Scheitelpunkts interessieren. Wenn wir also einen einzelnen Scheitelpunkt aus einem Graphen löschen, um wie viel kann sich die Cliquewidth verringern?$4*2^k$$k$

Ich werde versuchen, Ihre alte Frage zu beantworten, obwohl ich nicht sicher bin, ob meine Antwort schlüssig ist, aber Sie in die richtige Richtung weisen sollte.

Lassen Sie uns zuerst die lineare Clique-Breite diskutieren. Wenn ein Diagramm eine lineare Clique-Breite hat und man dem Diagramm 1 Scheitelpunkt hinzufügt , kann dieser Scheitelpunkt in der Reihenfolge immer mit einer eindeutigen Farbe an die erste Stelle gesetzt werden. Daher erhöht sich die lineare Cliquenbreite nur um höchstens 1, wenn Sie einen Scheitelpunkt hinzufügen.$k$$1$

Gurski und Wanke zeigten in "Zur Beziehung zwischen NLC-Breite und linearer NLC-Breite", dass Cographien eine unbegrenzte lineare Cliquenbreite haben.

Da cographs eine unbegrenzte lineare Cliquenbreite, aber eine begrenzte Cliquenbreite haben, muss jede gute Cliquenzerlegung eine Baumstruktur haben. Wir müssen zeigen, dass wir beliebig viele tiefe Äste erzwingen können. Jetzt machen wir es wie für Bäume: Konstruieren Sie einen Baum mit 2 ^ k Blättern und addieren Sie k Scheitelpunkten, und jedes Blatt ist mit einer eindeutigen Teilmenge neuer Scheitelpunkte verbunden.