Powody, dla których wykres może nie być

Rozważając nieco to pytanie , próbowałem zidentyfikować wszystkie różne powody, dla których wykres może nie być k kolorowy. Są to jedyne 2 powody, które udało mi się dotychczas zidentyfikować:$G = (V_G,E_G)$$k$

1. zawiera klikę o rozmiarze k + 1 . To oczywisty powód.$G$$k+1$

2. Istnieje podrozdział z G, taki że oba poniższe stwierdzenia są prawdziwe:$H = (V_H, E_H)$$G$

   • nie jest k - 1 do pokolorowania.$H$$k-1$
   • . Innymi słowy, nie istnieje węzeł X w G , ale nie w H tak, że x jest połączony z każdym węźle H .$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$$x$$G$$H$$x$$H$

Widzimy 2 powyższe powody jako reguły. Przez rekurencyjnie ich stosowania, tylko 2 sposoby budowania non colorable wykres, który nie zawiera k + 1 kliki są:$k$$k+1$

1. Zacznij od cyklu o równej długości (który jest pokolorowania), a następnie zastosuj regułę 2 dla k - 1 razy. Zauważ, że krawędź nie jest uważana za cykl o długości (w przeciwnym razie proces ten spowodowałby zbudowanie kliki ).$2$$k-1$k + $2$$k+1$
2. Zacznij od cyklu o nieparzystej długości (który jest pokolorowania), a następnie zastosuj regułę 2 dla k - 2 razy. Długość cyklu początkowego musi być większa niż 3 (w przeciwnym razie proces ten spowodowałby zbudowanie kliki k + 1 ).$3$$k-2$$3$$k+1$

Pytanie

Czy jest jakiś kolejny powód, inne niż te 2 powyżej, który sprawia, że wykres non colorable?$k$

$\ $
Aktualizacja 30/11/2012

Dokładniej, potrzebuję trochę twierdzenia o formie:

Wykres ma liczbę chromatyczną χ ( G ) = k + 1 wtedy i tylko wtedy, gdy ...$G$$\chi(G) = k + 1$

Rachunek Hajósa , na który zwrócił uwagę Yuval Filmus w swojej odpowiedzi, jest doskonałym przykładem tego, czego szukam, ponieważ wykres ma liczbę chromatyczną χ ( G ) = k + 1 wtedy i tylko wtedy, gdy można go wyprowadzić z aksjomatu K k + 1 poprzez wielokrotne stosowanie 2 reguł wnioskowania rachunku różniczkowego. Liczba Hajósa h ( G ) jest wówczas minimalną liczbą kroków niezbędnych do uzyskania G (tzn. Jest to długość najkrótszego dowodu).$G$$\chi(G) = k + 1$$K_{k+1}$$h(G)$$G$

To bardzo interesujące, że:

• Pytanie, czy istnieje wykres którego h ( G ) jest wykładniczy w rozmiarze G, jest nadal otwarte.$G$$h(G)$$G$
• Jeśli taki nie występują, a następnie N P = c o, N P .$G$$NP = coNP$

Powinieneś sprawdzić rachunek Hajósa . Hajós pokazał, że każdy wykres z liczbą chromatyczną co najmniej ma podgraph, który ma „powód” dla żądania k kolorów. Powodem tego jest system próbny wymagający k kolorów. Jedynym pewnikiem jest K k , a istnieją dwie zasady wnioskowania. Zobacz także ten artykuł Pitassi i Urquharta na temat wydajności tego systemu dowodowego.$k$$k$$k$$K_k$

Częściowa odpowiedź, ponieważ nie znam ładnego „powodu”, który można uogólnić, ale następujący wykres (bezwstydny nick tutaj ):

Nie jest 3-colorable, ale to oczywiście 4-colorable (jest płaska) i nie zawiera , ani cyklu z dodatkowym wierzchołka podłączony do wszystkich wierzchołków stopnia (chyba że czegoś mi brakuje, ale tylko wierzchołki połączone z wierzchołkiem, a jego sąsiad znajduje się w 3 cyklach). Idąc dalej, możesz zastosować wersję reguły 2, aby uzyskać wykres liczby chromatycznej 5.$K_{4}$

Podejrzewam, że dla każdego rodzaju istnieje wykres pewnej minimalnej liczby chromatycznej (patrz hipoteza Heawooda ), która nie jest zgodna z regułami 1 lub 2. Oczywiście nie mam dowodów innych niż intuicja.

Lovasz znalazł topologiczne przeszkody dla k-kolorowności i wykorzystał swoją teorię do rozwiązania hipotezy Knasera. Jego twierdzenie jest następujące. Niech G będzie połączonym wykresem, a N (G) będzie prostym kompleksem, którego twarze są podzbiorami V, które mają wspólnych sąsiadów. Następnie, jeśli N (K) jest połączony k (mianowicie wszystkie jego zredukowane grupy homologii wynoszą od 0 do wymiaru k-1), wówczas liczba kolorów potrzebnych do zabarwienia G wynosi co najmniej k + 3.

Brak dużego niezależnego zestawu może być tak samo ważny jak posiadanie dużej kliki.

Ważną przeszkodą dla niemożności kolorowania wykresu jest to, że maksymalny rozmiar niezależnego zestawu jest mniejszy niż n / k, gdzie n jest liczbą wierzchołków. To bardzo ważna przeszkoda. Na przykład oznacza to, że losowy wykres w G (n, 1/2) ma liczbę chromatyczną co najmniej n / log n.

Bardziej dopracowaną przeszkodą jest to, że dla każdego przypisania nieujemnych wag dla wierzchołków nie ma niezależnego zestawu, który uchwyciłby ułamek 1/5 (lub więcej) masy całkowitej. Pamiętaj, że obejmuje to również „brak przeszkód kliki”. LP-dualność mówi, że ta przeszkoda jest równoważna „ułamkowej liczbie chromatycznej” G większej niż k.

Istnieją również przeszkody dla k-zabarwienia o innym charakterze, które czasem wykraczają poza barierę ułamkowej liczby chromatycznej. Poświęcę im osobną odpowiedź.

$G$$\chi(G)=k+1$

$G$$\chi(G)\ge k$$G$$k-1$