Граф Ґрьоча

Граф Ґрьоча — граф без трикутників з 11 вершинами, 20 ребрами, хроматичним числом 4 і числом схрещень 5. Граф названо на честь німецького математика Герберта Ґрьоча і він демонструє необхідність припущення планарності в теоремі Ґрьоча (Grötzsch 1959), яка стверджує, що будь-який планарний граф без трикутників можна розфарбувати в 3 кольори. Граф Ґрьоча є членом нескінченної послідовності графів без трикутників, у якій кожен граф є мичельськіаном попереднього графа, починаючи від нуль-графа. Цю послідовність графів використав Мичельський (Mycielski, 1955), щоб показати, що існують графи без трикутників з довільно великим хроматичним числом. З цієї причини іноді граф Ґрьоча називають графом Мичельського або Мичельського — Ґрьоча. На відміну від інших, пізніших графів у послідовності, граф Ґрьоча є найменшим графом без трикутників з його хроматичним числом (Chvátal, 1974).

Хеггквіст (Häggkvist, 1981) використав модифіковану версію графа Ґрьоча для спростування гіпотези Ердеша і Симоновича (Erdős, Simonovits, 1973) про хроматичне число графів без трикутників, що мають великий степінь. Модифікація Хеггквіста полягає в заміні кожної з п'яти вершин степеня чотири графа Ґрьоча трьома вершинами і заміні кожної з п'яти вершин степеня три двома вершинами. Кожна з решти вершин п'ятого степеня замінюються чотирма вершинами. Дві вершини в цьому збільшеному графі з'єднані ребром, якщо відповідні їм вершини були з'єднані ребром у графі Ґрьоча. В результаті отримуємо 10-регулярний граф без трикутників з 29 вершинами і хроматичним числом 4, що спростовує гіпотезу, за якою не існує графа без трикутників з хроматичним числом 4 і n вершинами, у якому кожна вершина має більше ніж n/3 сусідів.

Граф Ґрьоча має хроматичний Індекс, рівний 5, радіус 2, обхват 4 і діаметр 2. Він є також 3-вершинно зв'язним і 3-k-реберно-зв'язним графом. Число незалежності графа дорівнює 5 і число домінування дорівнює 3.

Алгебричні властивості

Повна група автоморфізмів графа Ґрьоча ізоморфна діедральній групі D₅ десятого порядку, групі симетрій правильного п'ятикутника, що включає обертання і відбиття.

Характеристичним многочленом графа Ґрьоча є

$-(x-1)^{5}(x^{2}-x-10)(x^{2}+3x+1)^{2}.\$

Див. також

• Граф Хватала — ще один маленький граф без трикутників, розфарбовуваний у 4 кольори.

Література

• Chvátal. Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). — Berlin : Lecture Notes in Mathematics, Vol. 406, Springer-Verlag, 1974. — С. 243–246. — MR0360330..
• On a valence problem in extremal graph theory // Discrete Mathematics. — 1973. — Т. 5, вип. 4. — С. 323–334. — DOI:10.1016/0012-365X(73)90126-X. — MR0342429..
• Grötzsch. 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. — Т. 8. — С. 109–120. — MR0116320..
• Häggkvist. Odd cycles of specified length in nonbipartite graphs. — 1981. — С. 89–99. — MR0671908..
• Mycielski. Sur le coloriage des graphs // Colloq. Math.. — 1955. — Т. 3. — С. 161–162. — MR0069494..

Посилання

• Weisstein, Eric W. Граф Ґрьоча(англ.) на сайті Wolfram MathWorld.