Теорема Ґрьоча
Теорема Ґрьоча — твердження, що будь-який планарний граф без трикутників можна розфарбувати трьома кольорами. Згідно з теоремою про чотири фарби, вершини будь-якого графа, який можна намалювати на площині без перетинів ребер, можна розфарбувати не більше ніж у чотири різних кольори так, що будь-які два кінці будь-якого ребра матимуть різні кольори. За теоремою ж Ґрьоча достатньо лише три кольори для планарних графів, які не містять трьох пов'язаних одна з одною вершин.
Теорему названо ім'ям німецького математика Герберта Ґрьоча[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].
- ↑ Berge, 1960.
- ↑ а б Grünbaum, 1963.
- ↑ Thomassen, 2003.
- ↑ Glebov, Kostochka, Tashkinov, 2005.
- ↑ Steinberg, Younger, 1989.
- ↑ Asghar, 2012.
- ↑ Zdeněk, Kráľ, Thomas, 2009.
- ↑ The European Prize in Combinatorics. — University of Bergen, 2015. — September. Архівовано з джерела 20 серпня 2016. Процитовано 2015-09-16..
- ↑ Heckman, 2007.
- ↑ Naserasr, 2007, с. Theorem 11.
- ↑ Nešetřil, Ossona de Mendez, 2012.
- ↑ de Castro, Cobos, Dana, Márquez, 2002.
- ↑ Dvořák, Kawarabayashi, Thomas, (2009). Ранні роботи щодо алгоритмів для цієї задачі можна знайти в Kowalik, (2010).
- Zdeněk Dvořák, Daniel Kráľ, Robin Thomas. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. — 2009. — 16 червня. — arXiv:0911.0885. — Bibcode:.
- [1] — University of Bergen, 2015. Архівовано з джерела 20 серпня 2016
- Claude Berge. Les problèmes de colaration en théorie des graphs // Publ. Inst. Statist. Univ. Paris. — 1960. — Т. 9 (16 червня). — С. 123–160.. Как процитировано в Grünbaum, (1963).}}
- de Castro N., Cobos F. J., Dana J. C., Márquez A. Triangle-free planar graphs as segment intersection graphs // Journal of Graph Algorithms and Applications. — 2002. — Т. 6, вип. 1 (16 червня). — С. 7–26. — DOI:. Архівовано з джерела 3 грудня 2008. Процитовано 25 березня 2022.
- Zdeněk Dvořák, Ken-ichi Kawarabayashi, Robin Thomas. Three-coloring triangle-free planar graphs in linear time // Proc. 20th ACM-SIAM Symposium on Discrete Algorithms. — 2009. — С. 1176–1182. — Bibcode: Архівовано з джерела 18 жовтня 2012 Архівна копія від 18 жовтня 2012 на Wayback Machine
- Glebov A. N., Kostochka A. V., Tashkinov V. A. Smaller planar triangle-free graphs that are not 3-list-colorable // Discrete Mathematics. — 2005. — Т. 290, вип. 2–3 (16 червня). — С. 269–274. — DOI:.
- Richard Steinberg, Younger D. H. Grötzsch's Theorem for the projective plane // Ars Combinatoria. — 1989. — Т. 28 (16 червня). — С. 15–31.
- Herbert 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 (16 червня). — С. 109–120.
- Branko Grünbaum. Grötzsch's theorem on 3-colorings // Michigan Math. J.. — 1963. — Т. 10, вип. 3 (16 червня). — С. 303–310. — DOI:.
- Christopher Carl Heckman. Progress on Steinberg's Conjecture. — 2007. — 16 червня. Архівовано з джерела 22 липня 2012. Процитовано 2012-07-27.
- Łukasz Kowalik. Fast 3-coloring triangle-free planar graphs // Algorithmica. — 2010. — Т. 58, вип. 3 (16 червня). — С. 770–789. — DOI:. Архівовано з джерела 24 вересня 2020. Процитовано 25 березня 2022.
- Reza Naserasr. Homomorphisms and edge-colourings of planar graphs // Journal of Combinatorial Theory. — 2007. — Т. 97, вип. 3 (16 червня). — С. 394–400. — (Series B). — DOI:.
- Jaroslav Nešetřil, Patrice Ossona de Mendez. 2.5 Homomorphism Dualities // Sparsity. — Heidelberg : Springer, 2012. — Т. 28. — С. 15–16. — (Algorithms and Combinatorics) — ISBN 978-3-642-27874-7. — DOI:
- Carsten Thomassen. A short list color proof of Grötzsch’s theorem // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вип. 1 (16 червня). — С. 189–192. — DOI:.
- Nabiha Asghar. Grötzsch's Theorem // Master's Thesis, University of Waterloo. — 2012. — 16 червня. — DOI:. Архівовано з джерела 26 лютого 2019. Процитовано 25 березня 2022.
