Nieprawidłowe płaskie ubarwienie o wielkości elementu monochromatycznego

Rozluźnijmy trochę kolorystykę, tzn. Pozwalamy niewielkiej liczbie sąsiadujących wierzchołków na przypisanie tego samego koloru. Składnik monochromatyczny jest zdefiniowany jako składnik połączony w podsgrafie wywołany przez zestaw wierzchołków, które otrzymują ten sam kolor, a pytanie polega na zapytaniu o minimalną liczbę kolorów potrzebną do pokolorowania wykresu, tak aby największy składnik monochromatyczny miał nie więcej niż rozmiar . $\lambda$$C$
Tradycyjne zabarwienie można uznać za -kolorowanie w tym ustawieniu. Stąd znalezienie minimalnej liczby jest trudne dla NP dla płaskiego grafu. $[\lambda,1]$$\lambda$

Moje pytanie brzmi: co powiesz na -kolorowanie grafów płaskich , lub bardziej ogólnie, -kolorowanie dla ?$[\lambda,2]$$[\lambda,C]$$C \geq 2$

Może to być postrzegane jako podwójny problem, co jest badane przez Edwardsa i Farr , gdzie jest stała, a jeden został poproszony o znalezienie minimalnego rozmiaru .$\lambda$$C$

Dwukolorowe idealne dopasowanie w sześciennych grafach płaskich jest bardzo podobne do twojego problemu, który Schaefer stwierdził w swojej słynnej pracy twierdzącej o dychotomii jako NP-zupełny, chociaż nie przedstawił dowodu na sześcienne wykresy płaskie. Problem wymaga istnienia dwóch kolorów sześciennych grafów płaskich, tak że każdy wierzchołek ma dokładnie jednego sąsiada tego samego koloru co on sam.

EDYCJA: Wadliwa kolorystyka jest wersją decyzyjną twojego problemu. Wykres jest (k, d) -kolorowalny, jeśli można pokolorować wierzchołki za pomocą k kolorów, tak że żaden wierzchołek nie sąsiaduje z więcej niż d wierzchołkami tego samego koloru. Wykazano, że problem decyzyjny (2,1) - kolorowanie z defektami, które jest równoważne z twoim problemem optymalizacji, jest NP-zupełny nawet dla grafów płaskich .