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

11

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 . λdo
Tradycyjne zabarwienie można uznać za -kolorowanie w tym ustawieniu. Stąd znalezienie minimalnej liczby jest trudne dla NP dla płaskiego grafu. [λ,1]λ

Moje pytanie brzmi: co powiesz na -kolorowanie grafów płaskich , lub bardziej ogólnie, -kolorowanie dla ?[λ,2)][λ,do]do2)

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.λdo

Yixin Cao
źródło

Odpowiedzi:

3

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 .

Mohammad Al-Turkistany
źródło
Czym jest redukcja z „idealnego dwukolorowego dopasowania w sześciennych grafach płaskich” do problemu Yixin?
Idealne dopasowanie w dwóch kolorach to specjalny przypadek, w którym maksymalny rozmiar podłączonego komponentu jest dokładnie równy C.
Mohammad Al-Turkistany,
Dziękuję za odpowiedź, ale nie mogę się z tobą zgodzić. Podobnie jak w przypadku problemu „idealne dopasowanie do 2 kolorów w sześciennych grafach płaskich”, KAŻDY element musi mieć dokładnie 2. Ale moje pytanie wydaje się łatwiejsze.
Yixin Cao,
Tak, tęskniłem za tą różnicą.
Mohammad Al-Turkistany