Twierdzenie Grötzscha - Grötzsch's theorem

Trójkolorowy wykres planarny bez trójkątów

W matematycznej dziedzinie teorii grafów , Twierdzenie Grötzsch za to stwierdzenie, że każdy trójkąt wolne graf planarny może być barwiony z zaledwie trzech kolorach. Zgodnie z twierdzeniem o czterech kolorach , każdy wykres, który można narysować na płaszczyźnie bez przecinania krawędzi, może mieć swoje wierzchołki pokolorowane co najwyżej czterema różnymi kolorami, tak że dwa punkty końcowe każdej krawędzi mają różne kolory, ale tylko zgodnie z twierdzeniem Grötzscha W przypadku grafów planarnych, które nie zawierają trzech sąsiadujących ze sobą wierzchołków, potrzebne są trzy kolory.

Historia

Twierdzenie zostało nazwane na cześć niemieckiego matematyka Herberta Grötzscha , który opublikował swój dowód w 1959 roku. Oryginalny dowód Grötzscha był złożony. Berge (1960) próbował to uprościć, ale jego dowód był błędny.

W 2003 roku Carsten Thomassen wyprowadził alternatywny dowód z innego pokrewnego twierdzenia: każdy planarny wykres o obwodzie co najmniej pięciu można pokolorować według 3 list . Jednak samo twierdzenie Grötzscha nie rozciąga się od kolorowania do kolorowania list: istnieją wolne od trójkątów planarne grafy, które nie dają się pokolorować trzema listami. W 2012 roku Nabiha Asghar przedstawił nowy i znacznie prostszy dowód twierdzenia, który jest inspirowany pracą Thomassena.

W 1989 roku Richard Steinberg i Dan Younger podali pierwszy poprawny dowód w języku angielskim na podwójną wersję tego twierdzenia.

Większe klasy grafów

Nieco bardziej ogólny wynik jest prawdziwy: jeśli wykres planarny ma co najwyżej trzy trójkąty, to można go pokolorować w trzech kolorach. Jednak pełny wykres planarny K ₄ i nieskończenie wiele innych grafów planarnych zawierających K ₄ zawiera cztery trójkąty i nie można ich trójkolorować. W 2009 roku Dvořák , Kráľ i Thomas ogłosili dowód na inne uogólnienie, przypuszczone w 1969 roku przez L.Havela: istnieje stała d taka, że ​​jeśli graf planarny nie ma dwóch trójkątów w odległości d od siebie, to może być pokolorowane trzema kolorami. Praca ta stanowiła podstawę do przyznania Europejskiej Nagrody Kombinatoryki im . Dvořáka 2015 .

Twierdzenia nie można uogólnić na wszystkie wykresy niepłaskie bez trójkąta: nie każdy wykres bez trójkąta nieplanarnego jest trójkolorowy. W szczególności wykres Grötzscha i wykres Chvátala są grafami bez trójkątów, wymagającymi czterech kolorów, a Mycielskian to transformacja wykresów, które można wykorzystać do konstruowania wykresów bez trójkątów, które wymagają arbitralnie dużej liczby kolorów.

Twierdzenia nie można też uogólnić na wszystkie planarne grafy wolne od K ₄ : nie każdy wykres planarny wymagający 4 kolorów zawiera K ₄ . W szczególności istnieje planarny wykres bez 4 cykli, który nie może być trójkolorowy.

Faktoring poprzez homomorfizm

Trójkolorowy graf G można opisać homomorfizmem grafu od G do trójkąta K ₃ . W języku homomorfizmów twierdzenie Grötzscha stwierdza, że ​​każdy graf planarny bez trójkąta ma homomorfizm do K ₃ . Naserasr wykazał, że każdy planarny graf bez trójkąta ma również homomorfizm do wykresu Clebscha , 4-chromatycznego wykresu. Przez połączenie tych dwóch wyników można było wykazać, że każdy trójkąt wolne płaskie wykres ma homomorfizmem do trójkąta wolnej 3-colorable wykresie produkt tensorowy w K ₃ z wykresu Clebsch. Zabarwienie wykresu mogą być następnie odzyskany przez tworzenia tej homomorfizm z homomorfizmu z produktu tensora jego K ₃ czynnika. Jednak wykres Clebscha i jego iloczyn tensorowy z K ₃ są zarówno niepłaskie; nie istnieje graf planarny pozbawiony trójkątów, do którego można by odwzorować każdy inny graf planarny bez trójkątów za pomocą homomorfizmu.

Reprezentacja geometryczna

Wynik de Castro i wsp. (2002) łączy twierdzenie Grötzsch jest z przypuszczeniem Scheinerman jest w reprezentację płaskich wykresach jako wykresy przecięcia z odcinków . Udowodnili, że każdy wykres planarny bez trójkąta może być reprezentowany przez zbiór odcinków linii o trzech nachyleniach, tak że dwa wierzchołki wykresu sąsiadują ze sobą wtedy i tylko wtedy, gdy reprezentujące je odcinki linii się przecinają. Następnie można uzyskać trójkolorowy wykres, przypisując dwóm wierzchołkom ten sam kolor, ilekroć ich odcinki linii mają takie samo nachylenie.

Złożoność obliczeniowa

Biorąc pod uwagę wykres planarny bez trójkątów, można znaleźć trójkolorowy wykres w czasie liniowym .

Uwagi

Bibliografia

• Asghar, Nabiha (2012), „Twierdzenie Grötzscha” (PDF) , praca magisterska, University of Waterloo , doi : 10.13140 / RG.2.1.1326.9367 .
• Berge, Claude (1960), „Les problèmes de colaration en théorie des graphs”, Publ. Inst. Statystyk. Univ. Paryż , 9 : 123–160. Cytowany przez Grünbauma (1963) . CS1 maint: zniechęcony parametr ( link ) CS1 maint: postscript ( link )
• de Castro, N .; Cobos, FJ; Dana, JC; Márquez, A. (2002), „Triangle-free planar graphs as segment intersection graphs” (PDF) , Journal of Graph Algorithms and Applications , 6 (1): 7–26, doi : 10.7155 / jgaa.00043 , MR   1898201 .
• Dvořák, Zdeněk ; Kawarabayashi, Ken-ichi ; Thomas, Robin (2009), "Three-colour triangle-free triangle planar graphs in linear time", Proc. Natl. 20-ga ACM-SIAM Sympozjum dyskretnej Algorytmy (PDF) , pp 1176/82,. ArXiv : 1302,5121 , bibcode : 2013arXiv1302.5121D , archiwizowane z oryginałem (PDF) na 2012-10-18 , pobierane 2013-02-22 .
• Glebov, AN; Kostochka, AV; Tashkinov, VA (2005), „Smaller planar triangle-free graphs that are not 3-list-colorable”, Discrete Mathematics , 290 (2–3): 269–274, doi : 10.1016 / j.disc.2004.10.015 .
• Steinberg, Richard; Younger, DH (1989), „Twierdzenie Grötzscha dla płaszczyzny rzutowej”, Ars Combinatoria , 28 : 15–31 .
• Grötzsch, Herbert (1959), „Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel”, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109–120, MR   0116320 CS1 maint: zniechęcony parametr ( link ) .
• Grünbaum, Branko (1963), "Twierdzenie Grötzscha o trójkolorach", Michigan Math. J. , 10 (3) : 303–310 , doi : 10,1307 / mmj / 1028998916 , MR   0154274 CS1 maint: zniechęcony parametr ( link ) .
• Heckman, Christopher Carl (2007), Progress on Steinberg's Conjecture , zarchiwizowane z oryginału na 2012-07-22 , pobrane 2012-07-27 CS1 maint: zniechęcony parametr ( link ) .
• Kowalik, Łukasz (2010), „Fast 3-colouring triangle-free planar graphs” (PDF) , Algorithmica , 58 (3): 770–789, doi : 10.1007 / s00453-009-9295-2 .
• Naserasr, Reza (2007), "Homomorphism and edge-colourings of planar graphs", Journal of Combinatorial Theory , Series B, 97 (3): 394–400, doi : 10.1016 / j.jctb.2006.07.001 , MR   2305893 .
• Nešetřil, Jaroslav ; Ossona de Mendez Patrice (2012), "2,5 Homomorfizm dualnoÊci" Sparsity algorytmy i Kombinatoryka, 28 , Heidelberg. Springer, str, 15-16, doi : 10.1007 / 978-3-642-27875-4 , HDL : 10338 .dmlcz / 143192 , ISBN   978-3-642-27874-7 , MR   2920058 .
• Thomassen, Carsten (2003), „A short list colour proof of Grötzsch's theorem”, Journal of Combinatorial Theory, Series B , 88 (1): 189–192, doi : 10.1016 / S0095-8956 (03) 00029-7 CS1 maint: zniechęcony parametr ( link ) .