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 .
Tradycyjne zabarwienie można uznać za -kolorowanie w tym ustawieniu. Stąd znalezienie minimalnej liczby jest trudne dla NP dla płaskiego grafu.
Moje pytanie brzmi: co powiesz na -kolorowanie grafów płaskich , lub bardziej ogólnie, -kolorowanie dla ?
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 .C.