Теорема Ґрьоча

твердження, що будь-який планарний граф без трикутників можна розфарбувати трьома кольорами

Теорема Ґрьоча — твердження, що будь-який планарний граф без трикутників можна розфарбувати трьома кольорами. Згідно з теоремою про чотири фарби, вершини будь-якого графа, який можна намалювати на площині без перетинів ребер, можна розфарбувати не більше ніж у чотири різних кольори так, що будь-які два кінці будь-якого ребра матимуть різні кольори. За теоремою ж Ґрьоча достатньо лише три кольори для планарних графів, які не містять трьох пов'язаних одна з одною вершин.

3-розфарбування бідіакіс-куба, приклад вільного від трикутників планарного графа.

ІсторіяРедагувати

Теорему названо ім'ям німецького математика Герберта Ґрьоча[en], який опублікував доведення 1959 року. Оригінальне доведення Ґрьоча було складним. Берж[1] спробував спростити його, але його доведення містило помилки[2].

2003 року Карстен Томассен[3] дав альтернативне доведення, виходячи з пов'язаної теореми — будь-який планарний граф з обхватом щонайменше п'ять має спискове розфарбування в 3 кольори. Однак теорема Ґрьоча сама по собі не розширюється з розфарбування на спискове розфарбування — існують вільні від трикутників планарні графи, які не мають спискового розфарбування в 3 кольори[4]. 1989 року Річард Штайнберг і Ден Юнгер[5] надали перше правильне доведення англійською двоїстої версії цієї теореми. 2012 року Набіха Асгар[6] надав нове істотно простіше доведення теореми, надихнувшись роботою Томассена.

Більші класи графівРедагувати

Істинний дещо загальніший результат: якщо планарний граф має не більше трьох трикутників, то його можна розфарбувати в 3 кольори[2]. Однак планарний повний граф K4 і нескінченно багато інших планарних графів, що містять K4, містять чотири трикутники і не розфарбовуються в 3 кольори. 2009 року Дворак, Краль і Томас оголосили про доведення іншого узагальнення, гіпотезу про яке висловив 1969 року Л. Хавел: існує стала d така, що, якщо планарний граф має два трикутники на відстані не більше d, то граф можна розфарбувати в три кольори[7]. Частково ця робота стала підставою для Європейської премії з комбінаторики[en] Дворака 2015 року[8]

Теорему не можна узагальнити на всі непланарні графи без трикутників — не будь-який непланарний граф без трикутників можна розфарбувати в 3 кольори. Зокрема, граф Ґрьоча і граф Хватала є графами без трикутників, але вимагають чотирьох кольорів, а мичельськіан — це перетворення графів, яке можна використати для побудови графів без трикутників, для яких потрібно довільно велике число кольорів.

Теорему також не можна узагальнити на всі планарні вільні від K4 графи — не будь-який планарний граф, який вимагає 4 кольорів, містить K4. Зокрема, існує планарний граф без 4-циклів, який не можна розфарбувати в 3 кольори[9].

Розкладання за допомогою гомоморфізмівРедагувати

Розфарбування в 3 кольори графа G можна описати гомоморфізмом графів із G в трикутник K3. Мовою гомоморфізмів теорема Ґрьоча стверджує, що будь-який вільний від трикутників планарний граф має гомоморфізм графу K3. Насераср показав, що будь-який вільний від трикутників планарний граф також має гомоморфізм у граф Клебша, 4-хроматичний граф. Комбінуючи ці два результати можна показати, що будь-який вільний від трикутників планарний граф має гомоморфізм у вільний від трикутників розфарбовуваний у 3 кольори граф, тензорний добуток K3 з графом Клебша. Розфарбування графа можна тоді отримати суперпозицією цього гомоморфізму з гомоморфізмом із їх тензорного добутку в їхній K3 множник. Однак граф Клебша і його тензорний добуток з K3 не планарні. Не існує вільного від трикутників планарного графа, в який будь-який інший вільний від трикутників планарний граф можна відобразити гомоморфізмом[10][11].

Геометричне поданняРедагувати

Результат Кастро, Кобоса, Дана, Маркеса[12] комбінує теорему Ґрьоча з гіпотезою Шейнермана на поданнях планарних графів як графів перетинів відрізків. Вони довели, що будь-який вільний від трикутників планарний граф можна подати набором відрізків з трьома можливими нахилами, так що дві вершини графа суміжні тоді й лише тоді, коли відповідні відрізки перетинаються. 3-розфарбування графа можна тоді отримати, призначивши двом вершинам однаковий колір, якщо їхні відрізки мають однаковий нахил.

Обчислювальна складністьРедагувати

Якщо дано планарний граф без трикутників, 3-розфарбування графа можна отримати за лінійний час[13].

ПриміткиРедагувати

  1. Berge, 1960.
  2. а б Grünbaum, 1963.
  3. Thomassen, 2003.
  4. Glebov, Kostochka, Tashkinov, 2005.
  5. Steinberg, Younger, 1989.
  6. Asghar, 2012.
  7. Zdeněk, Kráľ, Thomas, 2009.
  8. The European Prize in Combinatorics. — University of Bergen, 2015. — September. Архівовано з джерела 20 серпня 2016. Процитовано 2015-09-16..
  9. Heckman, 2007.
  10. Naserasr, 2007, с. Theorem 11.
  11. Nešetřil, Ossona de Mendez, 2012.
  12. de Castro, Cobos, Dana, Márquez, 2002.
  13. Dvořák, Kawarabayashi, Thomas, (2009). Ранні роботи щодо алгоритмів для цієї задачі можна знайти в Kowalik, (2010).

ЛітератураРедагувати