Eine falsche planare Färbung mit monochromatischer Komponentengröße

11

Lassen Sie uns die Färbung ein wenig lockern, dh wir lassen zu, dass einer kleinen Anzahl benachbarter Scheitelpunkte dieselbe Farbe zugewiesen wird. Eine monochromatische Komponente ist definiert als eine verbundene Komponente in dem Teilgraphen, die durch den Satz von Eckpunkten induziert wird, die dieselbe Farbe erhalten, und die Frage besteht darin, nach der Mindestanzahl von FarbenλC zu fragen, die erforderlich sind, um einen Graphen so zu färben, dass die größte monochromatische Komponente die Größe hat nicht mehr als C .
Die traditionelle Färbung kann in dieser Einstellung als -Farbe betrachtet werden. Daher ist es für planare Graphen im Allgemeinen NP-schwer , die minimale Anzahl von λ zu finden . [λ,1]λ

Meine Frage ist, wie wäre es mit -Farben von planaren Graphen[λ,2] oder allgemeiner mit -Farben für C 2 ?[λ,C]C2

Dies kann als ein doppeltes Problem dessen angesehen werden, was von Edwards und Farr untersucht wird , wobei festgelegt ist und man gebeten wird, die Mindestgröße von C zu finden .λC

Yixin Cao
quelle

Antworten:

3

Die zweifarbige perfekte Übereinstimmung in kubischen planaren Graphen ist Ihrem Problem sehr ähnlich, das von Schäfer in seinem berühmten Dichotomie-Theorem als NP-vollständig angegeben wurde, obwohl er den Beweis für kubische planare Graphen nicht lieferte. Das Problem verlangt die Existenz von zwei Farben kubischer planarer Graphen, so dass jeder Scheitelpunkt genau einen Nachbarn hat, der dieselbe Farbe wie er selbst hat.

BEARBEITEN: Eine fehlerhafte Färbung ist die Entscheidungsversion Ihres Problems. Ein Graph ist (k, d) färbbar, wenn man die Scheitelpunkte mit k Farben so färben kann, dass kein Scheitelpunkt mehr als d Scheitelpunkten derselben Farbe benachbart ist. Das Entscheidungsproblem (2,1) - Färben mit Fehlern, das Ihrem Optimierungsproblem entspricht, hat sich auch für planare Graphen als NP-vollständig erwiesen .

Mohammad Al-Turkistany
quelle
Was ist eine Reduzierung von "2-farbiger perfekter Übereinstimmung in kubischen planaren Graphen" auf Yixins Problem?
Die zweifarbige perfekte Übereinstimmung ist ein Sonderfall, bei dem die maximale Größe der verbundenen Komponenten genau gleich C ist.
Mohammad Al-Turkistany
Vielen Dank für Ihre Antwort, aber ich kann Ihnen nicht zustimmen. Wie beim Problem "2-farbige perfekte Übereinstimmung in kubischen planaren Graphen" muss JEDE Komponente genau 2 sein. Aber meine Frage scheint einfacher zu sein.
Yixin Cao
Ja, ich habe diesen Unterschied verpasst.
Mohammad Al-Turkistany