Twierdzenie Brooksa
W teorii grafów twierdzenie Brooksa określa związek między maksymalnym stopniem grafu a jego liczbą chromatyczną . Zgodnie z twierdzeniem, w spójnym grafie, w którym każdy wierzchołek ma co najwyżej Δ sąsiadów, wierzchołki mogą być pokolorowane tylko kolorami Δ, z wyjątkiem dwóch przypadków, grafów pełnych i grafów cyklicznych o nieparzystej długości, które wymagają Δ + 1 kolorów.
Twierdzenie nosi imię R. Leonarda Brooksa , który opublikował jego dowód w 1941 roku. Kolorowanie z liczbą kolorów opisanych przez twierdzenie Brooksa jest czasami nazywane kolorowaniem Brooksa lub kolorowaniem Δ .
Oświadczenie formalne
Dla dowolnego połączonego nieskierowanego wykresu G o maksymalnym stopniu Δ liczba chromatyczna G wynosi co najwyżej Δ, chyba że G jest grafem pełnym lub nieparzystym cyklem, w którym to przypadku liczba chromatyczna wynosi Δ + 1 .
Dowód
László Lovász ( 1975 ) podaje uproszczony dowód twierdzenia Brooksa. Jeśli graf nie jest dwuspójny , jego dwupołączone składowe można pokolorować oddzielnie, a następnie połączyć kolorowania. Jeśli graf ma wierzchołek v o stopniu mniejszym niż Δ, to algorytm zachłannego kolorowania , który koloruje wierzchołki dalej od v przed bliższymi, używa co najwyżej kolorów Δ. Dzieje się tak, ponieważ w czasie, gdy każdy wierzchołek inny niż v jest kolorowy, przynajmniej jeden z jego sąsiadów (ten na najkrótszej ścieżce do v ) jest bezbarwny, więc ma mniej niż Δ kolorowych sąsiadów i ma dowolny kolor. Kiedy algorytm osiągnie v , jego niewielka liczba sąsiadów pozwala na pokolorowanie go. Dlatego najtrudniejszy przypadek dowodu dotyczy dwuspójnych Δ- regularnych grafów z Δ ≥ 3. W tym przypadku Lovász pokazuje, że można znaleźć takie drzewo rozpinające , że dwóch niesąsiadujących sąsiadów u i w korzenia v jest liśćmi w drzewie . Zachłanne kolorowanie rozpoczynające się od u i w i przetwarzające pozostałe wierzchołki drzewa rozpinającego w kolejności od dołu do góry, kończące się na v , wykorzystuje co najwyżej Δ kolorów. Ponieważ, gdy każdy wierzchołek inny niż v jest kolorowy, ma on niekolorowego rodzica, więc jego już pokolorowani sąsiedzi nie mogą wykorzystać wszystkich wolnych kolorów, podczas gdy w v dwaj sąsiedzi u i w mają równe kolory, więc znowu wolny kolor pozostaje dla v sam.
Rozszerzenia
Bardziej ogólna wersja twierdzenia dotyczy kolorowania list : mając dowolny spójny graf nieskierowany o maksymalnym stopniu Δ, który nie jest ani kliką , ani nieparzystym cyklem, oraz listę Δ kolorów dla każdego wierzchołka, można wybrać kolor dla każdego wierzchołek ze swojej listy, tak aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, lista chromatyczna liczby połączonego nieskierowanego grafu G nigdy nie przekracza Δ, chyba że G jest kliką lub nieparzystym cyklem. Zostało to udowodnione przez Vadima Vizinga ( 1976 ). Mała modyfikacja dowodu Lovásza dotyczy tego przypadku: dla tych samych trzech wierzchołków u , v , i w z tego dowodu albo nadaj u i w ten sam kolor co sobie nawzajem (jeśli to możliwe) lub w inny sposób podaj jeden z nich kolor niedostępny dla v , a następnie chciwie dokończ kolorowanie, jak poprzednio.
W przypadku niektórych wykresów może być potrzebnych nawet mniej niż Δ kolorów. Bruce Reed ( 1999 ) pokazuje, że Δ - 1 kolorów wystarczy wtedy i tylko wtedy, gdy dany graf nie ma Δ-kliki, pod warunkiem, że Δ jest wystarczająco duże. W przypadku grafów bez trójkątów lub bardziej ogólnie grafów, w których sąsiedztwo każdego wierzchołka jest wystarczająco rzadkie , wystarczą kolory O(Δ/log Δ).
Stopień wykresu pojawia się również w górnych granicach dla innych rodzajów kolorowania; w przypadku kolorowania krawędzi wynik, że indeks chromatyczny wynosi co najwyżej Δ + 1, jest twierdzeniem Vizinga . Rozszerzenie twierdzenia Brooksa na całkowite zabarwienie , stwierdzające, że całkowita liczba chromatyczna wynosi co najwyżej Δ + 2, zostało przypuszczane przez Mehdi Behzad i Vizing. Twierdzenie Hajnala – Szemerédiego o sprawiedliwym kolorowaniu stwierdza, że każdy wykres ma (Δ + 1) -kolorowanie, w którym rozmiary dowolnych dwóch klas kolorów różnią się co najwyżej o jeden.
Algorytmy
Kolorowanie Δ lub nawet kolorowanie listy Δ wykresu stopnia-Δ można znaleźć w czasie liniowym. Znane są również wydajne algorytmy do znajdowania kolorowań Brooksa w równoległych i rozproszonych modelach obliczeń.
Notatki
- Alon, Noga ; Krivelewicz, Michał ; Sudakov, Benny (1999), „Kolorowanie wykresów z rzadkimi sąsiedztwami”, Journal of Combinatorial Theory , Seria B, 77 (1): 73–82, doi : 10.1006 / jctb.1999.1910
- Brooks, RL (1941), „O kolorowaniu węzłów sieci”, Mathematical Proceedings of the Cambridge Philosophical Society , 37 (2): 194–197, doi : 10.1017 / S030500410002168X .
- Grable, David A.; Panconesi, Alessandro (2000), „Szybkie algorytmy dystrybucji dla kolorów Brooksa – Vizinga”, Journal of Algorithms , 37 : 85–120, doi : 10.1006 / jagm.2000.1097 .
- Hajnal, Piotr; Szemerédi, Endre (1990), „Brooks kolorowanie równolegle”, SIAM Journal on Discrete Mathematics , 3 (1): 74–80, doi : 10.1137/0403008 .
- Karloff, HJ (1989), „Algorytm NC dla twierdzenia Brooksa”, Theoretical Computer Science , 68 (1): 89–103, doi : 10.1016/0304-3975 (89) 90121-7 .
- Lovász, L. (1975), „Trzy krótkie dowody w teorii grafów”, Journal of Combinatorial Theory , seria B, 19 (3): 269–271, doi : 10.1016/0095-8956 (75) 90089-1 .
- Panconesi, Alessandro; Srinivasan, Aravind (1995), „Lokalny charakter Δ-kolorowania i jego zastosowania algorytmiczne”, Combinatorica , 15 (2): 255–280, doi : 10.1007 / BF01200759 .
- Reed, Bruce (1999), „Wzmocnienie twierdzenia Brooksa”, Journal of Combinatorial Theory , seria B, 76 (2): 136–149, doi : 10.1006/jctb.1998.1891 .
- Skulrattanakulchai, San (2006), „Kolorowanie wierzchołków Δ-List w czasie liniowym”, Information Processing Letters , 98 (3): 101–106, doi : 10.1016/j.ipl.2005.12.007 .
- Vizing, VG (1976), „Kolory wierzchołków z podanymi kolorami”, Diskret. Analizuj. (po rosyjsku), 29 : 3–10 .