Теорема Ґрьоча — твердження, що будь-який планарний граф без трикутників можна розфарбувати трьома кольорами. Згідно з теоремою про чотири фарби, вершини будь-якого графа, який можна намалювати на площині без перетинів ребер, можна розфарбувати не більше ніж у чотири різних кольори так, що будь-які два кінці будь-якого ребра матимуть різні кольори. За теоремою ж Ґрьоча достатньо лише три кольори для планарних графів, які не містять трьох пов'язаних одна з одною вершин.
Історія Теорему названо ім'ям німецького математика , який опублікував доведення 1959 року. Оригінальне доведення Ґрьоча було складним. Берж спробував спростити його, але його доведення містило помилки.
2003 року Карстен Томассен дав альтернативне доведення, виходячи з пов'язаної теореми — будь-який планарний граф з обхватом щонайменше п'ять має спискове розфарбування в 3 кольори. Однак теорема Ґрьоча сама по собі не розширюється з розфарбування на спискове розфарбування — існують вільні від трикутників планарні графи, які не мають спискового розфарбування в 3 кольори. 1989 року Річард Штайнберг і Ден Юнгер надали перше правильне доведення англійською двоїстої версії цієї теореми. 2012 року Набіха Асгар надав нове істотно простіше доведення теореми, надихнувшись роботою Томассена.
Більші класи графів Істинний дещо загальніший результат: якщо планарний граф має не більше трьох трикутників, то його можна розфарбувати в 3 кольори. Однак планарний повний граф K4 і нескінченно багато інших планарних графів, що містять K4, містять чотири трикутники і не розфарбовуються в 3 кольори. 2009 року Дворак, Краль і Томас оголосили про доведення іншого узагальнення, гіпотезу про яке висловив 1969 року Л. Хавел: існує стала d така, що, якщо планарний граф має два трикутники на відстані не більше d, то граф можна розфарбувати в три кольори. Частково ця робота стала підставою для Дворака 2015 року .
Теорему не можна узагальнити на всі непланарні графи без трикутників — не будь-який непланарний граф без трикутників можна розфарбувати в 3 кольори. Зокрема, граф Ґрьоча і граф Хватала є графами без трикутників, але вимагають чотирьох кольорів, а мичельськіан — це перетворення графів, яке можна використати для побудови графів без трикутників, для яких потрібно довільно велике число кольорів.
Теорему також не можна узагальнити на всі планарні вільні від K4 графи — не будь-який планарний граф, який вимагає 4 кольорів, містить K4. Зокрема, існує планарний граф без 4-циклів, який не можна розфарбувати в 3 кольори.
Розкладання за допомогою гомоморфізмів Розфарбування в 3 кольори графа G можна описати гомоморфізмом графів із G в трикутник K3. Мовою гомоморфізмів теорема Ґрьоча стверджує, що будь-який вільний від трикутників планарний граф має гомоморфізм графу K3. Насераср показав, що будь-який вільний від трикутників планарний граф також має гомоморфізм у граф Клебша, 4-хроматичний граф. Комбінуючи ці два результати можна показати, що будь-який вільний від трикутників планарний граф має гомоморфізм у вільний від трикутників розфарбовуваний у 3 кольори граф, тензорний добуток K3 з графом Клебша. Розфарбування графа можна тоді отримати суперпозицією цього гомоморфізму з гомоморфізмом із їх тензорного добутку в їхній K3 множник. Однак граф Клебша і його тензорний добуток з K3 не планарні. Не існує вільного від трикутників планарного графа, в який будь-який інший вільний від трикутників планарний граф можна відобразити гомоморфізмом.
Геометричне подання Результат Кастро, Кобоса, Дана, Маркеса комбінує теорему Ґрьоча з гіпотезою Шейнермана на поданнях планарних графів як графів перетинів відрізків. Вони довели, що будь-який вільний від трикутників планарний граф можна подати набором відрізків з трьома можливими нахилами, так що дві вершини графа суміжні тоді й лише тоді, коли відповідні відрізки перетинаються. 3-розфарбування графа можна тоді отримати, призначивши двом вершинам однаковий колір, якщо їхні відрізки мають однаковий нахил.
Обчислювальна складність Якщо дано планарний граф без трикутників, 3-розфарбування графа можна отримати за лінійний час. Ранні роботи щодо алгоритмів для цієї задачі можна знайти в ..
Примітки
Література
. Как процитировано в .}}
Архівна копія від 18 жовтня 2012 на Wayback Machine