Grötsch tétele az az állítás, hogy bármely háromszög nélküli síkgráf három színnel színezhető . A négy szín tétele szerint minden olyan gráf esetében, amely a síkban élek keresztezése nélkül rajzolható meg, maximum négy színnel színezheti ki a csúcsait úgy, hogy bármely él bármely két vége eltérő színű legyen. A Grötzsch-tétel szerint három összefüggő csúcsot nem tartalmazó síkgráfokhoz csak három szín elegendő.
A tétel nevét Herbert Grötsch német matematikusról kapta , aki 1959-ben publikálta a bizonyítást. Grötsch eredeti bizonyítása bonyolult volt. Berge [1] megpróbálta leegyszerűsíteni, de a bizonyítása hibákat tartalmazott [2] .
2003-ban Carsten Thomassen [3] adott egy alternatív bizonyítást, egy kapcsolódó tételből kiindulva – minden legalább ötös kerületű síkgráfnak van egy előírt 3 színezése . Maga Grötzsch tétele azonban nem terjed ki a színezéstől az előírt színezésig – vannak háromszög nélküli síkgráfok, amelyek nem rendelkeznek előírt 3 színnel [4] . 1989-ben Richard Steinberg és Dan Junger [5] adták az első helyes bizonyítékot angolul ennek a tételnek a kettős változatára. 2012-ben Nabiha Asghar [6] új és sokkal egyszerűbb bizonyítást adott a tételnek, amelyet Thomassen munkája inspirált.
Egy kicsit általánosabb eredmény igaz: ha egy síkgráfnak legfeljebb három háromszöge van, akkor 3 színnel színezhető [2] . Azonban a K 4 síkbeli teljes gráf és végtelen sok más, K 4 -et tartalmazó sík gráf négy háromszöget tartalmaz, és nem 3 színezhető. 2009-ben Dvorak, Kralj és Thomas bejelentették egy másik általánosítás bizonyítását, amelyet 1969-ben L. Havel sejtése javasolt: létezik olyan d állandó , hogy ha egy síkgráfnak két háromszöge van legfeljebb d távolságra , akkor a grafikon három színnel színezhető [ 7] . Ez a munka képezte a 2015 -ös Európai Dvorak Kombinatorika Díj alapját [8].
A tétel nem általánosítható minden háromszög nélküli nem síkbeli gráfra – nem minden háromszög nélküli nem síkbeli gráf háromszögű. Különösen a Grötzsch és Chwátala gráfok háromszög nélküli gráfok, de négy színt igényelnek, a Mycelski -gráf pedig egy olyan gráftranszformáció, amellyel tetszőlegesen sok színt igénylő háromszög nélküli gráfok készíthetők.
A tétel nem általánosítható minden sík K 4 -mentes gráfra – nem minden 4 színt igénylő síkgráf tartalmaz K 4 -et . Létezik 4 ciklus nélküli síkgráf, amely nem lehet 3 színű [9] .
A G gráf 3 színű színezése leírható egy gráfhomomorfizmussal G - ből K 3 háromszöggé . A homomorfizmusok nyelvén Grötzsch tétele kimondja, hogy bármely háromszög nélküli síkgráfnak van homomorfizmusa a K 3 gráfhoz . Nasserasr kimutatta, hogy minden háromszög nélküli síkgráfnak homomorfizmusa van a Clebsch-gráfhoz , egy 4-kromatikus gráfhoz. E két eredmény kombinálásával kimutatható, hogy bármely háromszög nélküli síkgráf homomorfizmussal rendelkezik egy háromszög nélküli, 3 színezhető gráfhoz, a K 3 tenzorszorzathoz a Clebsch gráfhoz. A gráf színezését ezután úgy kaphatjuk meg, hogy ezt a homomorfizmust a tenzorszorzatuk homomorfizmusával a K 3 faktorukra helyezzük . A Clebsch-gráf és tenzorszorzata K 3 -mal azonban nem síkbeli. Nincs olyan háromszög nélküli síkgráf, amelybe bármely más háromszög nélküli síkgráf homomorfizmussal leképezhető [10] [11] .
Castro, Cobos, Dan, Marquez [12] eredménye egyesíti a Grötzsch-tételt a Scheinerman-sejtésekkel a síkgráfok szegmensmetszés gráfokként való ábrázolásáról . Bebizonyították, hogy bármely háromszög nélküli síkgráf ábrázolható három lehetséges meredekségű szakaszok halmazával úgy, hogy két gráfcsúcs akkor és csak akkor van szomszédos, ha az ábrázoló szakaszok metszik egymást. A gráf 3-as színezése akkor érhető el, ha két csúcsnak azonos színűt rendelünk, ha a szakaszaik ugyanolyan meredekségűek.
Adott egy sík háromszög nélküli gráf, a gráf 3-as színezése érhető el lineáris időben [13] .