Grötschs teorem er påstanden om, at enhver trekantfri plan graf kan farves med tre farver. Ifølge firefarvesætningen er det for enhver graf, der kan tegnes i planet uden at krydse kanter, muligt at farve sine hjørner med højst fire forskellige farver, så to ender af enhver kant har forskellige farver. Ifølge Grötzsch-sætningen er kun tre farver tilstrækkelige til plane grafer, der ikke indeholder tre forbundne hjørner.
Sætningen er opkaldt efter den tyske matematiker Herbert Grötsch , som offentliggjorde beviset i 1959. Grötschs originale bevis var kompliceret. Berge [1] forsøgte at forenkle det, men hans bevis indeholdt fejl [2] .
I 2003 gav Carsten Thomassen [3] et alternativt bevis, ud fra en relateret sætning - enhver plan graf med en omkreds på mindst fem har en foreskrevet 3-farve . Selve Grötzschs sætning strækker sig dog ikke fra en farvning til en foreskrevet farvning – der er trekantsfrie plane grafer, som ikke har en foreskrevet 3-farvefarvning [4] . I 1989 gav Richard Steinberg og Dan Junger [5] det første korrekte bevis på engelsk for den dobbelte version af denne teorem. I 2012 gav Nabiha Asghar [6] et nyt og meget enklere bevis på sætningen, inspireret af Thomassens arbejde.
Et lidt mere generelt resultat er sandt: Hvis en plan graf højst har tre trekanter, så kan den farves med 3 farver [2] . Imidlertid indeholder den plane komplette graf K 4 og uendeligt mange andre plane grafer, der indeholder K 4 , fire trekanter og er ikke 3-farvelige. I 2009 annoncerede Dvorak, Kralj og Thomas beviset for en anden generalisering, som blev foreslået i 1969 af L. Havels formodning: der eksisterer en konstant d , sådan at hvis en plan graf har to trekanter i en afstand på højst d , så grafen kan farvelægges med tre farver [7] . Dette arbejde udgjorde en del af grundlaget for 2015 European Dvorak Combinatorics Prize [8]
Sætningen kan ikke generaliseres til alle ikke-plane grafer uden trekanter - ikke alle ikke-plane grafer uden trekanter er 3-farvelige. Især Grötzsch- og Chwátala -graferne er trekantfrie grafer, men kræver fire farver, og Mycelskian er en graftransformation, der kan bruges til at konstruere trekantfrie grafer, der kræver et vilkårligt stort antal farver.
Sætningen kan heller ikke generaliseres til alle plane K 4 -frie grafer – ikke enhver plan graf, der kræver 4 farver, indeholder K 4 . Især eksisterer der en plan graf uden 4-cyklusser, der ikke kan være 3-farvet [9] .
En 3-farvet farvning af en graf G kan beskrives ved en grafhomomorfi fra G til en trekant K 3 . I homomorfisproget siger Grötzschs sætning, at enhver trekantfri plan graf har en homomorfi til grafen K 3 . Nasserasr viste, at enhver trekantfri plan graf også har en homomorfi til Clebsch-grafen , en 4-kromatisk graf. Ved at kombinere disse to resultater kan det vises, at enhver trekantfri plan graf har en homomorfi til en trekantfri 3-farverbar graf, K 3 - tensorproduktet med Clebsch-grafen. Graffarvningen kan derefter opnås ved at overlejre denne homomorfi med homomorfi fra deres tensorprodukt til deres K 3 faktor. Clebsch-grafen og dens tensorprodukt med K 3 er dog ikke plane. Der er ingen trekantfri plan graf, hvori enhver anden trekantfri plan graf kan kortlægges ved en homomorfi [10] [11] .
Resultatet af Castro, Cobos, Dan, Marquez [12] kombinerer Grötzsch-sætningen med Scheinerman-formodningen om repræsentationer af plane grafer som segmentskæringsgrafer . De beviste, at enhver trekantfri plan graf kan repræsenteres af et sæt linjestykker med tre mulige hældninger, således at to grafhjørner støder op til hinanden, hvis og kun hvis de repræsenterende linjestykker skærer hinanden. En 3-farvning af en graf kan så opnås ved at tildele to hjørner samme farve, hvis deres linjestykker har samme hældning.
Givet en plan trekantfri graf, kan en 3-farvning af grafen opnås i lineær tid [13] .