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

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$\lambda$$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 . $[\lambda,1]$$\lambda$

Meine Frage ist, wie wäre es mit -Farben von planaren Graphen$[\lambda,2]$ oder allgemeiner mit -Farben für C ≥ 2 ?$[\lambda,C]$$C \geq 2$

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 .$\lambda$$C$

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 .