Teorema lui Grötsch este afirmația că orice graf planar fără triunghi poate fi colorat cu trei culori. Conform teoremei celor patru culori , pentru orice grafic care poate fi desenat în plan fără muchii încrucișate, este posibil să-și coloreze vârfurile cu cel mult patru culori diferite, astfel încât oricare două capete ale oricărei muchii să aibă culori diferite. Conform teoremei Grötzsch, doar trei culori sunt suficiente pentru grafurile plane care nu conțin trei vârfuri conectate.
Teorema este numită după matematicianul german Herbert Grötsch , care a publicat demonstrația în 1959. Dovada originală a lui Grötsch a fost complicată. Berge [1] a încercat să o simplifice, dar dovada sa conținea erori [2] .
În 2003, Carsten Thomassen [3] a dat o demonstrație alternativă, pornind de la o teoremă înrudită — orice graf planar cu circumferința de cel puțin cinci are o culoare prescrisă de trei . Cu toate acestea, teorema lui Grötzsch în sine nu se extinde de la o colorare la o colorare prescrisă - există grafice plane fără triunghi care nu au o colorare prescrisă în 3 culori [4] . În 1989, Richard Steinberg și Dan Junger [5] au dat prima dovadă corectă în limba engleză a versiunii duale a acestei teoreme. În 2012, Nabiha Asghar [6] a dat o nouă și mult mai simplă demonstrație a teoremei, inspirată din lucrarea lui Thomassen.
Un rezultat puțin mai general este adevărat: dacă un graf plan are cel mult trei triunghiuri, atunci este colorabil cu 3 culori [2] . Totuși, graficul complet planar K 4 și nenumărate alte grafice plane care conțin K 4 conțin patru triunghiuri și nu sunt 3-colorabile. În 2009, Dvorak, Kralj și Thomas au anunțat demonstrarea unei alte generalizări, care a fost propusă în 1969 de conjectura lui L. Havel: există o constantă d astfel încât dacă un graf plan are două triunghiuri la o distanță de cel mult d , atunci graficul poate fi colorat cu trei culori [7] . Această lucrare a făcut parte din baza Premiului European Dvorak Combinatorics 2015 [8]
Teorema nu poate fi generalizată la toate graficele neplanare fără triunghiuri - nu orice grafic neplanar fără triunghiuri este 3-colorabil. În special, graficele Grötzsch și Chwátala sunt grafice fără triunghi, dar necesită patru culori, iar Mycelskian este o transformare grafică care poate fi folosită pentru a construi grafice fără triunghi care necesită un număr arbitrar de mare de culori.
De asemenea, teorema nu poate fi generalizată la toate graficele plane fără K 4 — nu orice grafic planar care necesită 4 culori conține K 4 . În special, există un grafic plan fără 4 cicluri care nu poate fi tricolorat [9] .
O colorare în trei culori a unui grafic G poate fi descrisă printr -un homomorfism de grafic din G într-un triunghi K 3 . În limbajul homomorfismelor, teorema lui Grötzsch afirmă că orice graf planar fără triunghi are un homomorfism la graful K 3 . Nasserasr a arătat că orice graf planar fără triunghi are, de asemenea, un homomorfism la graful Clebsch , un graf 4-cromatic. Prin combinarea acestor două rezultate, se poate demonstra că orice graf planar fără triunghi are un homomorfism la un graf cu 3 culori fără triunghi, produsul tensor K 3 cu graficul Clebsch. Colorarea graficului poate fi apoi obținută prin suprapunerea acestui homomorfism cu homomorfismul din produsul lor tensor în factorul lor K3 . Totuși, graficul Clebsch și produsul său tensor cu K 3 nu sunt plane. Nu există un graf planar fără triunghi în care orice alt graf plan fără triunghi să poată fi mapat printr-un homomorfism [10] [11] .
Rezultatul lui Castro, Cobos, Dan, Marquez [12] combină teorema Grötzsch cu conjectura Scheinerman privind reprezentările grafurilor plane ca grafuri de intersecție a segmentelor . Ei au demonstrat că orice graf planar fără triunghi poate fi reprezentat printr-un set de segmente de dreaptă cu trei pante posibile, astfel încât două vârfuri de graf sunt adiacente dacă și numai dacă segmentele de drepte reprezentative se intersectează. O 3-colorare a unui grafic poate fi apoi obținută prin atribuirea a două vârfuri de aceeași culoare dacă segmentele lor de linie au aceeași pantă.
Având în vedere un grafic fără triunghi plan, se poate obține o 3-colorare a graficului în timp liniar [13] .