Grötzschs sats - Grötzsch's theorem
I matematiska området grafteori , Grötzsch teorem är påståendet att varje triangel fria plana graf kan färgas med endast tre färger. Enligt fyrfärgssatsen kan varje graf som kan ritas i planet utan kantkorsningar ha sina hörn färgade med högst fyra olika färger, så att de två ändpunkterna för varje kant har olika färger, men enligt Grötzschs sats bara tre färger behövs för plana grafer som inte innehåller tre intilliggande hörn.
Historia
Satsen är uppkallad efter den tyska matematikern Herbert Grötzsch , som publicerade sitt bevis 1959. Grötzschs ursprungliga bevis var komplicerat. Berge (1960) försökte förenkla det men hans bevis var felaktigt.
År 2003 härledde Carsten Thomassen ett alternativt bevis från en annan relaterad teorem: varje plan graf med minst fem omkrets är 3-lista-färgbar . Grötzschs sats sträcker sig dock inte från färgning till listfärgning: det finns triangelfria plana grafer som inte är 3-lista-färgbara. 2012 gav Nabiha Asghar ett nytt och mycket enklare bevis på satsen som är inspirerad av Thomassens arbete.
1989 gav Richard Steinberg och Dan Younger det första korrekta beviset på engelska av den dubbla versionen av denna sats.
Större klasser av diagram
Ett något mer allmänt resultat är sant: om en plan graf har högst tre trianglar är den 3-färgbar. Emellertid, den plana komplett graf K 4 , och oändligt många andra plana grafer innehållande K 4 , innehåller fyra trianglar och är inte 3-PLAUSIBEL. 2009 tillkännagav Dvořák , Kráľ och Thomas ett bevis på en annan generalisering, antagen 1969 av L. Havel: det finns en konstant d sådan att, om en plan graf inte har två trianglar inom avstånd d från varandra, då kan den vara färgade med tre färger. Detta arbete utgjorde en del av grunden för Dvořáks europeiska pris 2015 i kombinatorik .
Satsen kan inte generaliseras till alla icke-plana triangelfria grafer: inte alla icke-plana triangelfria diagram är 3-färgbara. I synnerhet är Grötzsch-grafen och Chvátal-grafen triangelfria grafer som kräver fyra färger, och Mycielskian är en omvandling av grafer som kan användas för att konstruera triangelfria grafer som kräver godtyckligt höga färger.
Satsen kan inte generaliseras till alla plan K 4 -fria grafer, antingen inte varje plan kurva som kräver 4 färger innehåller K 4 . I synnerhet finns det en plan graf utan 4-cykler som inte kan vara trefärgade.
Faktorisering genom en homomorfism
En 3-färgning av en graf G kan beskrivas med en grafhomomorfi från G till en triangel K 3 . På homomorfismens språk säger Grötzschs sats att varje triangelfri plan graf har en homomorfism till K 3 . Naserasr visade att varje triangelfri plan graf också har en homomorfism till Clebsch-grafen , en 4-kromatisk graf. Genom att kombinera dessa två resultat kan det visas att varje triangelfri plan graf har en homomorfism till en triangelfri 3-färgbar graf, tensorprodukten av K 3 med Clebsch-grafen. Färgning av grafen kan sedan utvinnas genom att komponera denna homomorfism med homomorfism från denna tensor produkt till dess K 3 faktor. Emellertid Clebsch grafen och dess tensorprodukt med K 3 är båda icke-plana; det finns inte ett triangelfritt plandiagram till vilket alla andra triangelfria plana diagram kan kartläggas av en homomorfism.
Geometrisk representation
Ett resultat av de Castro et al. (2002) kombinerar Grötzschs teorem med Scheinermans antagande om framställning av plana grafer som skärningsdiagram över linjesegment . De bevisade att varje triangelfri plan graf kan representeras av en samling linjesegment med tre lutningar, så att två hörn i diagrammet ligger intill om och endast om linjesegmenten som representerar dem korsar. En trefärgning av diagrammet kan sedan erhållas genom att tilldela två hörn i samma färg när deras linjesegment har samma lutning.
Beräkningskomplexitet
Med en triangelfri plan graf kan en trefärgning av grafen hittas linjärt .
Anteckningar
Referenser
- Asghar, Nabiha (2012), "Grötzsch's Theorem" (PDF) , magisteruppsats, 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. Statistik. Univ. Paris , 9 : 123–160. Som citerad av Grünbaum (1963) . CS1 maint: avskräckt parameter ( länk ) CS1 maint: postscript ( länk )
- de Castro, N .; Cobos, FJ; Dana, JC; Márquez, A. (2002), "Triangelfria plana grafer som segmentkorsningsdiagram" (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), "Trefärgade triangelfria plana grafer i linjär tid", Proc. 20: e ACM-SIAM-symposiet om diskreta algoritmer (PDF) , s. 1176–1182, arXiv : 1302.5121 , Bibcode : 2013arXiv1302.5121D , arkiverat från originalet (PDF) 2012-10-18 , hämtad 2013-02-22 .
- Glebov, AN; Kostochka, AV; Tashkinov, VA (2005), "Mindre plana triangelfria grafer som inte är 3-lista-färgbara", Diskret matematik , 290 (2–3): 269–274, doi : 10.1016 / j.disc.2004.10.015 .
- Steinberg, Richard; Yngre, DH (1989), "Grötzschs sats för det projektiva planet", 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: avskräckt parameter ( länk ) .
- Grünbaum, Branko (1963), "Grötzsch's teorem on 3-colorings", Michigan Math. J. , 10 (3): 303–310, doi : 10.1307 / mmj / 1028998916 , MR 0154274 CS1 maint: avskräckt parameter ( länk ) .
- Heckman, Christopher Carl (2007), Progress on Steinberg's Conjecture , arkiverad från originalet 2012-07-22 , hämtad 2012-07-27 CS1 maint: avskräckt parameter ( länk ) .
- Kowalik, Łukasz (2010), "Snabb 3-färgning triangel fria plana grafer" (PDF) , Algorithmica , 58 (3): 770-789, doi : 10,1007 / s00453-009-9295-2 .
- Naserasr, Reza (2007), "Homomorfismer och kantfärgning av plana grafer", Journal of Combinatorial Theory , serie 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 Homomorphism Dualities", Sparsity , Algorithms and Combinatorics, 28 , Heidelberg: Springer, s. 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 color 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: avskräckt parameter ( länk ) .