Wie viele verschiedene Farben sind erforderlich, um die Auswahlmöglichkeiten eines Diagramms zu verringern?

39

Ein Graph ist -choosable (auch bekannt als K -Liste-färbbar ) , wenn für jede Funktion f , die Scheitelpunkte auf Sätze von Karten k Farben, gibt es eine Farbzuordnung c , so dass für alle Knoten v , c ( v ) f ( v ) , und derart , daß für alle Kanten v w , c ( v ) c ( w ) .kkfkcvc(v)f(v)vwc(v)c(w)

Nehmen wir nun an, dass ein Graph nicht k- auswählbar ist. Das heißt, es gibt eine Funktion f von Eckpunkten zu k- Tupeln von Farben, die keine gültige Farbzuordnung c hat . Was ich wissen möchte ist, wie wenig Farben insgesamt benötigt werden? Wie klein kann v G f ( v ) sein? Gibt es eine Zahl N ( k ) (unabhängig von G ), so dass wir garantiert ein nicht färbbares f finden können , das nur N ( k ) verschiedene Farben verwendet?GkfkcvGf(v)N(k)GfN(k)

Die Relevanz für CS ist, dass wir , wenn existiert, die k- Auswählbarkeit für konstantes k in einfach exponentieller Zeit testen können (versuchen Sie einfach alle ( N ( k )N(k)kkWahlen vonf, und für jedes prüfen Sie, ob es in der ZeitknnO(1)gefärbt werden kann,wohingegen sonst etwas, das schneller wächst, wienkn, erforderlich sein könnte.(N(k)k)nfknnO(1)nkn

David Eppstein
quelle
1
Gibt es ein Beispiel für N (k)> 2k-1?
Yaroslav Bulatov
1
Mein erster Gedanke ist, zu versuchen, die Anzahl der Farben, die in dem Standardbeispiel erforderlich sind, zu verringern, damit zweiteilige Graphen eine beliebig hohe listenchromatische Zahl haben können. Die Anzahl der Farben in der Liste in dieser Konstruktion ist jedoch exponentiell zu dem erreichten . Ich habe mir jedoch nicht genügend Zeit genommen, um die Untergrenze zu beweisen (also ist dies noch keine Antwort ...). k
Derrick Stolee
1
Es könnte sich lohnen, diese ausgezeichnete Frage auch auf MathOverflow zu posten ...
François G. Dorais
Beantwortet das Setzen von in Korollar 1.4 hier zumindest einen Teil Ihrer Frage? k=1
Aaron Sterling
@ Aaron: Ich bin nicht sicher, was du meinst. Wenn ich in dieser Konsequenz k = 1 setze, scheint es zu sagen, dass die Auswahlzahl höchstens die chromatische Zahl multipliziert mit einem logarithmischen Faktor ist; aber es scheint nicht viel darüber zu sagen, wie viele verschiedene Farben für diese Wahlnummer benötigt werden.
David Eppstein

Antworten:

21

Daniel Král und Jiří Sgall haben Ihre Frage verneint. Aus der Zusammenfassung ihres Papiers:

G(k,)L(v)|L(v)|kvV(G)|vV(G)L(v)|3kG(k,)(k,+1)

N(k)k3N(2)=4N(1)=1

Daniel Král, Jiří Sgall: Diagramme aus Listen mit begrenzter Größe ihrer Vereinigung ausmalen . Journal of Graph Theory 49 (3): 177-186 (2005)

Serge Gaspers
quelle
Beeindruckend. Dies regelt die Frage, wenn auch negativ. Vielen Dank @Serge! Und ich wünschte, ich könnte auch Daniel und Jiří danken!
Hsien-Chih Chang 張顯 之
Ich hätte mir auch eine positive Antwort auf die Frage gewünscht.
Serge Gaspers
8

Als ein bisschen unverschämte Eigenwerbung fanden Marthe Bonamy und ich negativere Antworten. Insbesondere Theorem 4 von http://arxiv.org/abs/1507.03495 verbessert in bestimmten Fällen das oben erwähnte Ergebnis von Král 'und Sgall. Die Beispiele, die wir verwenden, sind vollständige zweiteilige Graphen, für deren Analyse wir einige Extremalkombinatoren verwendet haben.

Die Arbeit wurde zum Teil durch diese TCS-Überlauffrage motiviert.

RJK
quelle