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

История

Теорема названа именем немецкого математика , опубликовавшего доказательство в 1959 году. Оригинальное доказательство Грёча было сложным. Берж попытался упростить его, но его доказательство содержало ошибки .

В 2003 году Карстен Томассен дал альтернативное доказательство, отталкиваясь от связанной теоремы — любой планарный граф с обхватом по меньшей мере пять имеет предписанную раскраску в 3 цвета . Однако теорема Грёча сама по себе не распространяется с раскраски на предписанную раскраску — существуют свободные от треугольников планарные графы, не имеющие предписанной раскраски в 3 цвета . В 1989 году Ричард Штайнберг и Дэн Юнгер дали первое верное доказательство двойственной версии этой теоремы. В 2012 году Набиха Асгар дал новое существенно более простое доказательство теоремы, вдохновившись работой Томассена.

Более крупные классы графов

Верен слегка более общий результат: если планарный граф имеет не более трёх треугольников, то он раскрашиваем в 3 цвета . Однако планарный полный граф K ₄ и бесконечно много других планарных графов, содержащих K ₄ , содержат четыре треугольника и не раскрашиваемы в 3 цвета. В 2009 Дворак, Краль и Томас объявили о доказательстве другого обобщения, о котором высказал в 1969 гипотезу Л. Хавел: существует константа d такая, что, если планарный граф имеет два треугольника на расстоянии не более d , то граф может быть раскрашен в три цвета . Эта работа составила часть базиса для европейской премии по комбинаторике Дворака 2015 года

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

Теорему также нельзя обобщить на все планарные свободные от K ₄ графы — не любой планарный граф, который требует 4 цветов, содержит K ₄ . В частности, существует планарный граф без 4-циклов, который не может быть раскрашен в 3 цвета .

Разложение посредством гомоморфизмов

Раскраска в 3 цвета графа G может быть описана гомоморфизмом графов из G в треугольник K ₃ . На языке гомоморфизмов теорема Грёча утверждает, что любой свободный от треугольников планарный граф имеет гомоморфизм графу K ₃ . Насераср показал, что любой свободный от треугольников планарный граф также имеет гомоморфизм в граф Клебша , 4-хроматический граф. Путём комбинации этих двух результатов можно показать, что любой свободный от треугольников планарный граф имеет гомоморфизм в свободный от треугольников в раскрашиваемый в 3 цвета граф, тензорное произведение K ₃ с графом Клебша. Раскраска графа может быть тогда получена путём суперпозиции этого гомоморфизма с гомоморфизмом из их тензорного произведения в их K ₃ множитель. Однако граф Клебша и его тензорное произведение с K ₃ не планарны. Не существует свободный от треугольников планарный граф, в которые любой другой свободный от треугольников планарный граф может быть отображён гомоморфизмом .

Геометрическое представление

Результат Кастро, Кобоса, Дана, Маркеса комбинирует теорему Грёча с гипотезой Шейнермана на представлениях планарных графов как графов пересечений отрезков . Они доказали, что любой свободный от треугольников планарный граф может быть представлен набором отрезков с тремя возможными наклонами, так что две вершины графа смежны тогда и только тогда, когда представляющие отрезки пересекаются. 3-раскраска графа может быть тогда получена путём назначения двум вершинам одинакового цвета, если их отрезки имеют одинаковый наклон.

Вычислительная сложность

Если дан планарный граф без треугольников, 3-раскраска графа может быть получена за линейное время .

Примечания

Литература

• Zdeněk Dvořák, Daniel Kráľ, Robin Thomas . Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. — 2009. — Bibcode : . — arXiv : .
• . — 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 . . Как процитировано в harvtxt error: якоря не существует: CITEREFGrünbaum1963 ( помощь ) .}}
• de Castro N., Cobos F. J., Dana J. C., Márquez A. // . — 2002. — Т. 6 , вып. 1 . — С. 7–26 . — doi : .
• Zdeněk Dvořák, Ken-ichi Kawarabayashi, Robin Thomas . Three-coloring triangle-free planar graphs in linear time // . — 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 : .
• 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 : .
• Christopher Carl Heckman. . — 2007. 22 июля 2012 года.
• Łukasz Kowalik. // Algorithmica. — 2010. — Т. 58 , вып. 3 . — С. 770–789 . — doi : .
• Reza Naserasr. Homomorphisms and edge-colourings of planar graphs // Journal of Combinatorial Theory . — 2007. — Т. 97 , вып. 3 . — С. 394–400 . — 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 . — С. 189–192 . — doi : .
• Nabiha Asghar. // Master's Thesis, University of Waterloo. — 2012. — doi : .