Теорема Грёча

Перейти к навигацииПерейти к поиску
3-раскраска бидиакис-куба, пример свободного от треугольников планарного графа.

Теорема Грёча — утверждение, что любой планарный граф без треугольников может быть раскрашен в три цвета. Согласно теореме о четырёх красках, для любого графа, который может быть нарисован на плоскости без пересечения рёбер, можно раскрасить его вершины не более чем в четыре различных цвета так, что любые два конца любого ребра имеют различные цвета. По теореме же Грёча достаточно лишь три цвета для планарных графов, которые не содержат трёх связанных друг с другом вершин.

История

Теорема названа именем немецкого математика Герберта Грёча[англ.], опубликовавшего доказательство в 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].

Примечания

  1. ↑ Berge, 1960.
  2. ↑ 1 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. — Сентябрь. Архивировано 20 августа 2016 года..
  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).

Литература

  • Zdeněk Dvořák, Daniel Kráľ, Robin Thomas. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. — 2009. — Bibcode: 2009arXiv0911.0885D. — arXiv:0911.0885.
  • The European Prize in Combinatorics. — University of Bergen, 2015.
  • Claude Berge. Les problèmes de colaration en théorie des graphs // Publ. Inst. Statist. Univ. Paris. — 1960. — Т. 9. — С. 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. — С. 7–26. — doi:10.7155/jgaa.00043.
  • 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. Архивная копия от 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. — С. 269–274. — doi:10.1016/j.disc.2004.10.015.
  • Richard Steinberg, Younger D. H. Grötzsch's Theorem for the projective plane // Ars Combinatoria. — 1989. — Т. 28. — С. 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. — С. 109–120.
  • Branko Grünbaum. Grötzsch'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.
  • 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:10.1007/978-3-642-27875-4.
  • Carsten Thomassen. A short list color proof of Grötzsch’s theorem // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вып. 1. — С. 189–192. — doi:10.1016/S0095-8956(03)00029-7.
  • Nabiha Asghar. Grötzsch's Theorem // Master's Thesis, University of Waterloo. — 2012. — doi:10.13140/RG.2.1.1326.9367.