wykresy, w których kolorowanie wierzchołków jest w P, ale niezależny zestaw jest NP kompletny

Czy istnieje przykład klasy grafów, dla których problem kolorowania wierzchołków występuje w P, ale zestaw niezależny jest problemem, czy NP jest kompletny?

Być może bardziej ogólne stwierdzenie (z łatwym dowodem) jest takie, że następujący problem jest już NP-zupełny:

Dane wejściowe: wykres G, 3-kolorowanie G, liczba całkowita k.

Pytanie: Czy G ma niezależny zestaw wielkości k?

Można to udowodnić poprzez redukcję z zestawu niezależnego. Zauważ, że jeśli weźmiemy wykres G, wybierzmy krawędź i podzielimy ją dwukrotnie (tj. Zastąpmy krawędź {u, v} ścieżką u, x, y, v, gdzie xiy mają stopień drugi), to liczba niezależności G wzrasta dokładnie o jeden. (Możesz dodać dokładnie jeden z x lub y do dowolnego zestawu, który był niezależny w G, a odwrotność też nie jest trudna.) Zatem pytanie, czy wykres G z m krawędziami ma niezależny zestaw wielkości k, jest równoważne pytaniu czy G ', który jest wynikiem dwukrotnego podzielenia wszystkich krawędzi w G, ma niezależny zestaw wielkości k + m. Ale zauważ, że łatwo jest uzyskać 3-kolorowanie G ', dzieląc G' na trzy niezależne zestawy w następujący sposób: jeden zawiera wierzchołki, które również były w G, a pozostałe dwie klasy zawierają dokładnie jedną z dwóch „ dzielnik ” wierzchołki dla każdej krawędzi. Stąd ta procedura konstruuje wykres G 'z jego 3-kolorowaniem, tak że obliczenie jego numeru niezależności daje ci numer niezależności oryginalnego wykresu G.

Podobno odniesienie „U-zupełne problemy na 3-połączonym sześciennym grafie planarnym i ich zastosowania” autorstwa Uehary (papieru, którego tak naprawdę nie widziałem) dowodzi, że niezależny zestaw jest NP-kompletny nawet dla płaskich grafów bez trójkątów. Ale według twierdzenia Grötzscha są one zawsze trójkolorowe, a testowanie mniejszej liczby kolorów niż 3 jest łatwe na każdym wykresie, więc można je optymalnie pokolorować w P.

Wykresy kołowe mają odwrotną właściwość: dla nich kolorowanie jest NP kompletne, ale problem z niezależnym zestawem jest łatwy.

To nie jest nowa odpowiedź, ale raczej wyjaśnienie pierwszego i łatwego do uzyskania odniesienia do twardości NIEZALEŻNEGO ZESTAWU w pozbawionych trójkątów sześciennych wykresach płaskich: Notatka Owena Murphy'ego, Obliczanie niezależnych zbiorów na wykresach z dużym obwodem , Discrete Applied Mathematics 35 (1992) 167-170 to potwierdza

$n$$cn^k$$c>0$$k, 0\le k < 1$

$c$$c>0$

Redukcja wskazana przez @BartJansen jest szczególnym przypadkiem w dowodzie jego twierdzenia Murphy'ego.

W przypadku przeciwnej właściwości wykresy liniowe wydają się być bardziej naturalne niż wykresy kołowe, jak to rozwiązał @DavidEppstein. W przypadku wykresów liniowych KOLOROWANIE jest kompletne z NP, ale NIEZALEŻNY ZESTAW jest łatwy.