Граф Ґрьоча
Граф Ґрьоча — граф без трикутників з 11 вершинами, 20 ребрами, хроматичним числом 4 і числом схрещень 5. Граф названо на честь німецького математика Шаблон:Не перекладено і він демонструє необхідність припущення планарності в теоремі Ґрьоча (Grötzsch 1959), яка стверджує, що будь-який планарний граф без трикутників можна розфарбувати в 3 кольори. Граф Ґрьоча є членом нескінченної послідовності графів без трикутників, у якій кожен граф є мичельськіаном попереднього графа, починаючи від Шаблон:Не перекладено. Цю послідовність графів використав Шаблон:Нп Шаблон:Harvard citation, щоб показати, що існують графи без трикутників з довільно великим хроматичним числом. З цієї причини іноді граф Ґрьоча називають графом Мичельського або Мичельського — Ґрьоча. На відміну від інших, пізніших графів у послідовності, граф Ґрьоча є найменшим графом без трикутників з його хроматичним числом Шаблон:Harvard citation.
Хеггквіст Шаблон:Harvard citation використав модифіковану версію графа Ґрьоча для спростування гіпотези Ердеша і Симоновича Шаблон:Harvard citation про хроматичне число графів без трикутників, що мають великий степінь. Модифікація Хеггквіста полягає в заміні кожної з п'яти вершин степеня чотири графа Ґрьоча трьома вершинами і заміні кожної з п'яти вершин степеня три двома вершинами. Кожна з решти вершин п'ятого степеня замінюються чотирма вершинами. Дві вершини в цьому збільшеному графі з'єднані ребром, якщо відповідні їм вершини були з'єднані ребром у графі Ґрьоча. В результаті отримуємо 10-регулярний граф без трикутників з 29 вершинами і хроматичним числом 4, що спростовує гіпотезу, за якою не існує графа без трикутників з хроматичним числом 4 і n вершинами, у якому кожна вершина має більше ніж n/3 сусідів.
Граф Ґрьоча має хроматичний Індекс, рівний 5, радіус 2, обхват 4 і діаметр 2. Він є також 3-вершинно зв'язним і 3-k-реберно-зв'язним графом. Число незалежності графа дорівнює 5 і число домінування дорівнює 3.
Алгебричні властивості
Повна група автоморфізмів графа Ґрьоча ізоморфна діедральній групі D5 десятого порядку, групі симетрій правильного п'ятикутника, що включає обертання і відбиття.
Характеристичним многочленом графа Ґрьоча є
Див. також
- Граф Хватала — ще один маленький граф без трикутників, розфарбовуваний у 4 кольори.