Grötschův teorém je tvrzení, že každý rovinný graf bez trojúhelníků může být obarven třemi barvami. Podle teorému o čtyřech barvách je pro každý graf, který lze nakreslit v rovině bez křížení hran, možné obarvit jeho vrcholy nejvýše čtyřmi různými barvami, takže libovolné dva konce libovolné hrany mají různé barvy. Pro rovinné grafy, které neobsahují tři spojené vrcholy, stačí podle Grötzschovy věty pouze tři barvy.
Věta je pojmenována po německém matematikovi Herbertu Grötschovi , který publikoval důkaz v roce 1959. Grötschův původní důkaz byl komplikovaný. Berge [1] se to snažil zjednodušit, ale jeho důkaz obsahoval chyby [2] .
V roce 2003 Carsten Thomassen [3] podal alternativní důkaz, vycházející ze související věty – každý rovinný graf s obvodem alespoň pět má předepsané 3 zbarvení . Samotný Grötzschův teorém však nezasahuje od zbarvení k předepsanému zbarvení – existují rovinné grafy bez trojúhelníků, které nemají předepsané 3barevné zbarvení [4] . V roce 1989 podali Richard Steinberg a Dan Junger [5] první správný důkaz v angličtině duální verze této věty. V roce 2012 podala Nabiha Asghar [6] nový a mnohem jednodušší důkaz teorému, inspirovaný prací Thomassena.
Platí trochu obecnější výsledek: má-li rovinný graf nejvýše tři trojúhelníky, pak je obarvitelný 3 barvami [2] . Rovinný úplný graf K 4 a nekonečně mnoho dalších rovinných grafů obsahujících K 4 však obsahují čtyři trojúhelníky a nejsou 3-barevné. V roce 2009 oznámili Dvořák, Kralj a Thomas důkaz dalšího zobecnění, které navrhla v roce 1969 domněnka L. Havla: existuje konstanta d taková, že pokud má rovinný graf dva trojúhelníky ve vzdálenosti nejvýše d , pak graf lze vybarvit třemi barvami [7] . Tato práce tvořila součást základu pro Evropskou cenu Dvořákova kombinatorika za rok 2015 [8]
Větu nelze zobecnit na všechny nerovinné grafy bez trojúhelníků - ne každý nerovinný graf bez trojúhelníků je 3-barevný. Zejména grafy Grötzsch a Chwátala jsou grafy bez trojúhelníků, ale vyžadují čtyři barvy, a Mycelskian je grafová transformace, kterou lze použít ke konstrukci grafů bez trojúhelníků, které vyžadují libovolně velký počet barev.
Větu také nelze zobecnit na všechny rovinné grafy bez K 4 – ne každý rovinný graf, který vyžaduje 4 barvy, obsahuje K 4 . Konkrétně existuje rovinný graf bez 4-cyklů, který nemůže být 3barevný [9] .
3-barevné zbarvení grafu G lze popsat homomorfismem grafu z G do trojúhelníku K 3 . V jazyce homomorfismů Grötzschova věta říká, že každý rovinný graf bez trojúhelníku má homomorfismus ke grafu K 3 . Nasserasr ukázal, že jakýkoli rovinný graf bez trojúhelníků má také homomorfismus s Clebschovým grafem , 4-chromatickým grafem. Kombinací těchto dvou výsledků lze ukázat, že jakýkoli rovinný graf bez trojúhelníků má homomorfismus k 3 vybarvitelnému grafu bez trojúhelníků, součin tenzoru K 3 s Clebschovým grafem. Zbarvení grafu lze pak získat superpozicí tohoto homomorfismu s homomorfismem z jejich tenzorového součinu do jejich faktoru K3 . Clebschův graf a jeho tenzorový součin s K 3 však nejsou rovinné. Neexistuje žádný rovinný graf bez trojúhelníků, do kterého by se dal pomocí homomorfismu zobrazit jakýkoli jiný rovinný graf bez trojúhelníků [10] [11] .
Výsledek Castra, Cobose, Dana, Marqueze [12] kombinuje Grötzschův teorém se Scheinermanovou domněnkou o reprezentaci rovinných grafů jako grafů průniku segmentů . Dokázali, že každý rovinný graf bez trojúhelníků může být reprezentován sadou úseček se třemi možnými sklony, takže dva vrcholy grafu sousedí právě tehdy, když se reprezentující úsečky protínají. 3-barevné zbarvení grafu pak lze získat přiřazením dvou vrcholů stejné barvy, pokud jejich úsečky mají stejný sklon.
Za předpokladu rovinného grafu bez trojúhelníků lze získat 3-barevné zbarvení grafu v lineárním čase [13] .