Hrabě Grecha

Grötzschův  graf je graf bez trojúhelníku s 11 vrcholy, 20 hranami, chromatickým číslem 4 a křížením 5. Graf je pojmenován po německém matematikovi Herbertu Grötzschovi a demonstruje potřebu předpokladu rovinnosti v Grötzschově větě ( Grötzsch 1959), který uvádí, že každý rovinný graf bez trojúhelníků může být obarven 3 barvami. Grötzschův graf je členem nekonečné posloupnosti grafů bez trojúhelníků, ve kterých je každý graf mycelským grafem předchozího grafu, počínaje nulovým grafem . Tuto sekvenci grafů použil Mycielski ( 1955 ), aby ukázal, že existují grafy bez trojúhelníků s libovolně velkým chromatickým číslem. Z tohoto důvodu se někdy hrabě Gröcz nazývá hrabě Mycielski nebo Mycielski-Gröcz. Na rozdíl od jiných, pozdějších grafů v posloupnosti je Grötschův graf svým chromatickým číslem nejmenším grafem bez trojúhelníku ( Chvátal 1974 ).

Häggkvist ( Häggkvist 1981 ) použil upravenou verzi Grötzschova grafu k vyvrácení domněnky Erdőse a Simonovitse ( Erdős, Simonovits 1973 ) o chromatickém počtu grafů bez trojúhelníků většího stupně. Heggquistova modifikace spočívá v nahrazení každého z pětistupňových čtyř vrcholů Grötzschova grafu třemi vrcholy a nahrazení každého z pětistupňových tří vrcholů dvěma vrcholy. Každý ze zbývajících vrcholů pátého stupně je nahrazen čtyřmi vrcholy. Dva vrcholy v tomto zvětšeném grafu jsou spojeny hranou, pokud jejich odpovídající vrcholy byly spojeny hranou v Groetschově grafu. Výsledkem je 10 - pravidelný graf bez trojúhelníků s 29 vrcholy a chromatickým číslem 4, což vyvrací hypotézu, že neexistuje graf bez trojúhelníků s chromatickým číslem 4 a n vrcholy, ve kterých by každý vrchol měl více než n /3 sousedů.

Grötzschův graf má chromatický index 5, poloměr 2, obvod 4 a průměr 2. Je to také graf s 3 vrcholy a 3 k-hranami . Číslo nezávislosti grafu je 5 a číslo dominance je 3.

Algebraické vlastnosti

Kompletní skupina automorfismu Grötzschova grafu je izomorfní k dihedrální grupě desátého řádu D 5 , grupě symetrie pravidelného pětiúhelníku , včetně rotace a odrazu.

Charakteristickým polynomem Grötschova grafu je

Viz také

• Count Khvatala  je další malý 4barevný graf bez trojúhelníků.

Literatura

• Chvátal. Grafy a kombinatorika (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag. — S. 243–246 . .
• K valenčnímu problému v extrémní teorii grafů // Diskrétní matematika . - 1973. - V. 5 , čís. 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. Liché cykly zadané délky v nebipartitních grafech. — S. 89–99 . .
• Mycielski. Sur le coloriage des graphs // Colloq. Matematika.. - 1955. - T. 3 . — S. 161–162 . .

Odkazy

• Weisstein, Eric W. Grötzsch Graph  (anglicky) na webových stránkách Wolfram MathWorld .