Меню Главная Случайная статья Настройки Теорема Грёча Материал из https://ru.wikipedia.org Теорема Грёча — утверждение, что любой планарный граф без треугольников может быть раскрашен в три цвета. Согласно теореме о четырёх красках, для любого графа, который может быть нарисован на плоскости без пересечения рёбер, можно раскрасить его вершины не более чем в четыре различных цвета так, что любые два конца любого ребра имеют различные цвета. По теореме же Грёча достаточно лишь три цвета для планарных графов, которые не содержат трёх связанных друг с другом вершин. Содержание 1 История 2 Более крупные классы графов 3 Разложение посредством гомоморфизмов 4 Геометрическое представление 5 Вычислительная сложность 6 Примечания 7 Литература История Теорема названа именем немецкого математика Герберта Грёча[англ.], опубликовавшего доказательство в 1959 году. Оригинальное доказательство Грёча было сложным. Берж[1] попытался упростить его, но его доказательство содержало ошибки[2]. В 2003 году Карстен Томассен[3] дал альтернативное доказательство, отталкиваясь от связанной теоремы — любой планарный граф с обхватом по меньшей мере пять имеет предписанную раскраску в 3 цвета. Однако теорема Грёча сама по себе не распространяется с раскраски на предписанную раскраску — существуют свободные от треугольников планарные графы, не имеющие предписанной раскраски в 3 цвета[4]. В 1989 году Ричард Штайнберг и Дэн Юнгер[5] дали первое верное доказательство двойственной версии этой теоремы. В 2012 году Набиха Асгар[6] дал новое существенно более простое доказательство теоремы, вдохновившись работой Томассена. Более крупные классы графов Верен слегка более общий результат: если планарный граф имеет не более трёх треугольников, то он раскрашиваем в 3 цвета[2]. Однако планарный полный граф K4 и бесконечно много других планарных графов, содержащих K4, содержат четыре треугольника и не раскрашиваемы в 3 цвета. В 2009 Дворак, Краль и Томас объявили о доказательстве другого обобщения, о котором высказал в 1969 гипотезу Л. Хавел: существует константа d такая, что, если планарный граф имеет два треугольника на расстоянии не более d, то граф может быть раскрашен в три цвета[7]. Эта работа составила часть базиса для европейской премии по комбинаторике Дворака 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. 1 2 Grnbaum, 1963. Thomassen, 2003. Glebov, Kostochka, Tashkinov, 2005. Steinberg, Younger, 1989. Asghar, 2012. Zdenk, Kr, Thomas, 2009. The European Prize in Combinatorics. — University of Bergen, 2015. — Сентябрь. Архивировано 20 августа 2016 года.. Heckman, 2007. Naserasr, 2007, с. Theorem 11. Neetil, Ossona de Mendez, 2012. de Castro, Cobos, Dana, Mrquez, 2002. Dvok, Kawarabayashi, Thomas (2009) harvtxt error: якоря не существует: CITEREFDvok,_Kawarabayashi,_Thomas2009 (помощь). Ранние работы по алгоритмам для этой задачи можно найти в Kowalik (2010) harvtxt error: якоря не существует: CITEREFKowalik2010 (помощь). Литература Zdenk Dvok, Daniel Kr, Robin Thomas. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. — 2009. — . — arXiv:0911.0885. The European Prize in Combinatorics. — University of Bergen, 2015. Claude Berge. Les problmes de colaration en thorie des graphs // Publ. Inst. Statist. Univ. Paris. — 1960. — Т. 9. — С. 123–160.. Как процитировано в Grnbaum (1963) harvtxt error: якоря не существует: CITEREFGrnbaum1963 (помощь).}} de Castro N., Cobos F. J., Dana J. C., Mrquez A. Triangle-free planar graphs as segment intersection graphs // Journal of Graph Algorithms and Applications. — 2002. — Т. 6, вып. 1. — С. 7–26. — doi:10.7155/jgaa.00043. 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. — С. 269–274. — doi:10.1016/j.disc.2004.10.015. Richard Steinberg, Younger D. H. Grtzsch's Theorem for the projective plane // Ars Combinatoria. — 1989. — Т. 28. — С. 15–31. Herbert Grtzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz fr dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. — 1959. — Т. 8. — С. 109–120. Branko Grnbaum. Grtzsch's theorem on 3-colorings // Michigan Math. J.. — 1963. — Т. 10, вып. 3. — С. 303–310. — doi:10.1307/mmj/1028998916. Christopher Carl Heckman. Progress on Steinberg's Conjecture. — 2007. Архивировано 22 июля 2012 года. ukasz Kowalik. Fast 3-coloring triangle-free planar graphs // Algorithmica. — 2010. — Т. 58, вып. 3. — С. 770–789. — doi:10.1007/s00453-009-9295-2. Reza Naserasr. Homomorphisms and edge-colourings of planar graphs // Journal of Combinatorial Theory. — 2007. — Т. 97, вып. 3. — С. 394–400. — doi:10.1016/j.jctb.2006.07.001. Carsten Thomassen. A short list color proof of Grtzsch’s theorem // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вып. 1. — С. 189–192. — doi:10.1016/S0095-8956(03)00029-7. Nabiha Asghar. Grtzsch's Theorem // Master's Thesis, University of Waterloo. — 2012. — doi:10.13140/RG.2.1.1326.9367.