Grötschs teorem är påståendet att varje triangelfri plan graf kan färgas med tre färger. Enligt fyrafärgssatsen är det för alla grafer som kan ritas i planet utan att korsa kanter möjligt att färga dess hörn med högst fyra olika färger så att alla två ändar av valfri kant har olika färger. Enligt Grötzsch-satsen räcker endast tre färger för plana grafer som inte innehåller tre sammankopplade hörn.
Teoremet är uppkallat efter den tyske matematikern Herbert Grötsch , som publicerade beviset 1959. Grötschs ursprungliga bevis var komplicerat. Berge [1] försökte förenkla det, men hans bevis innehöll fel [2] .
År 2003 gav Carsten Thomassen [3] ett alternativt bevis, med utgångspunkt från en relaterad teorem - varje plan graf med omkrets minst fem har en föreskriven 3-färgning . Grötzschs sats i sig sträcker sig dock inte från en färgning till en föreskriven färgsättning – det finns triangelfria plana grafer som inte har en föreskriven 3-färgsfärgning [4] . 1989 gav Richard Steinberg och Dan Junger [5] det första korrekta beviset på engelska för den dubbla versionen av detta teorem. 2012 gav Nabiha Asghar [6] ett nytt och mycket enklare bevis på satsen, inspirerad av Thomassens arbete.
Ett lite mer allmänt resultat är sant: om en plan graf har högst tre trianglar, så är den färgbar med 3 färger [2] . Den plana kompletta grafen K 4 och oändligt många andra plana grafer som innehåller K 4 innehåller dock fyra trianglar och är inte 3-färgbara. 2009 tillkännagav Dvorak, Kralj och Thomas beviset för en annan generalisering, som föreslogs 1969 av L. Havels gissning: det finns en konstant d så att om en plan graf har två trianglar på ett avstånd av högst d , då grafen kan färgas med tre färger [7] . Detta arbete utgjorde en del av grunden för 2015 års europeiska Dvorak Combinatorics-pris [8]
Satsen kan inte generaliseras till alla icke-planära grafer utan trianglar - inte alla icke-planära grafer utan trianglar är 3-färgbara. I synnerhet är Grötzsch- och Chwátala- graferna triangelfria grafer men kräver fyra färger, och Mycelskian är en graftransformation som kan användas för att konstruera triangelfria grafer som kräver ett godtyckligt stort antal färger.
Satsen kan inte heller generaliseras till alla plana K 4 -fria grafer – inte alla plana grafer som kräver 4 färger innehåller K 4 . I synnerhet finns det en plan graf utan 4-cykler som inte kan vara 3-färgad [9] .
En 3-färgsfärgning av en graf G kan beskrivas med en grafhomomorfism från G till en triangel K 3 . På homomorfis språk säger Grötzschs teorem att varje triangelfri plan graf har en homomorfism till grafen K 3 . Nasserasr 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, K 3 - tensorprodukten med Clebsch-grafen. Graffärgningen kan sedan erhållas genom att överlagra denna homomorfism med homomorfismen från deras tensorprodukt till deras K3 -faktor . Clebsch-grafen och dess tensorprodukt med K 3 är emellertid inte plana. Det finns ingen triangelfri plan graf i vilken vilken annan triangelfri plan graf som helst kan kartläggas genom en homomorfism [10] [11] .
Resultatet av Castro, Cobos, Dan, Marquez [12] kombinerar Grötzsch-satsen med Scheinermans gissningar om representationer av plana grafer som segmentskärningsgrafer . De visade att vilken triangelfri plan graf som helst kan representeras av en uppsättning linjesegment med tre möjliga lutningar, så att två grafens hörn ligger intill om och endast om de representerande linjesegmenten skär varandra. En 3-färgning av en graf kan sedan erhållas genom att tilldela två hörn samma färg om deras linjesegment har samma lutning.
Givet en plan triangelfri graf kan en 3-färgning av grafen erhållas i linjär tid [13] .