Contele Grecha

 Graficul Grötzsch este un grafic fără triunghi cu 11 vârfuri, 20 de muchii, numărul cromatic 4 și numărul de încrucișare 5. Graficul este numit după matematicianul german Herbert Grötzsch și demonstrează necesitatea ipotezei planarității în teorema lui Grötzsch ( Grötzsch 1959), care afirmă că orice graf plan fără triunghiuri poate fi colorat cu 3 culori. Graficul Grötzsch este membru al unei secvențe infinite de grafice fără triunghi, în care fiecare grafic este Mycelskian al graficului anterior, pornind de la graficul nul . Această secvență de grafice a fost folosită de Mycielski ( 1955 ) pentru a arăta că există grafice fără triunghi cu un număr cromatic arbitrar mare. Din acest motiv, uneori contele Gröcz este numit contele Mycielski sau Mycielski-Gröcz. Spre deosebire de alte grafice ulterioare din secvență, graficul Grötsch este cel mai mic grafic fără triunghi cu numărul său cromatic ( Chvátal 1974 ).

Häggkvist ( Häggkvist 1981 ) a folosit o versiune modificată a graficului Grötzsch pentru a respinge conjectura lui Erdős și Simonovits ( Erdős, Simonovits 1973 ) despre numărul cromatic al graficelor fără triunghiuri de grad mai mare. Modificarea lui Heggquist este de a înlocui fiecare dintre cele cinci grade patru vârfuri ale graficului Grötzsch cu trei vârfuri și de a înlocui fiecare dintre cele cinci grade trei vârfuri cu două vârfuri. Fiecare dintre vârfurile rămase de gradul cinci sunt înlocuite cu patru vârfuri. Două vârfuri din acest grafic mărit sunt conectate printr-o muchie dacă vârfurile lor corespunzătoare au fost conectate printr-o muchie în graficul Groetscha. Rezultatul este un grafic 10 - fără triunghi obișnuit cu 29 de vârfuri și număr cromatic 4, care respinge ipoteza că nu există un grafic fără triunghi cu număr cromatic 4 și n vârfuri în care fiecare vârf are mai mult de n /3 vecini.

Graficul Grötzsch are indicele cromatic 5, raza 2, circumferința 4 și diametrul 2. Este, de asemenea, un graf conectat cu 3 vârfuri și cu muchii 3 -k . Numărul de independență al graficului este 5, iar numărul de dominanță este 3.

Proprietăți algebrice

Grupul complet de automorfism al grafului Grötzsch este izomorf cu grupul diedric de ordinul al zecelea D 5 , grupul de simetrie al unui pentagon regulat , incluzând rotația și reflexia.

Polinomul caracteristic al grafului Grötsch este

Vezi și

• Contele Khvatala  este un alt grafic mic de 4 culori fără triunghiuri.

Literatură

• Chvatal. Grafice și combinatorie (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). Berlin: Note de curs în matematică, vol. 406, Springer-Verlag. — S. 243–246 . .
• Despre o problemă de valență în teoria grafurilor extreme // Matematică discretă . - 1973. - V. 5 , nr. 4 . — S. 323–334 . - doi : 10.1016/0012-365X(73)90126-X . .
• Grotzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. - 1959. - T. 8 . — S. 109–120 . .
• Haggkvist. Cicluri impare de lungime specificată în grafice nebipartite. — S. 89–99 . .
• Mycielski. Sur le coloriage des graphs // Coloq. Matematică.. - 1955. - T. 3 . — S. 161–162 . .

Link -uri

• Weisstein, Eric W. Grötzsch Graph  (engleză) pe site-ul web Wolfram MathWorld .