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

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

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. 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. — Сентябрь..
  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).

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.