Теорема Грёча - Grötzschs theorem

3-раскраска плоского графа без треугольников

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

История

Теорема названа в честь немецкого математика. Герберт Грётч, который опубликовал свое доказательство в 1959 году. Первоначальное доказательство Гретча было сложным. Берже (1960) попытался упростить его, но его доказательство было ошибочным.[1]

В 2003 году Карстен Томассен[2] получил альтернативное доказательство из другой связанной теоремы: каждый плоский граф с обхват по крайней мере пять 3-лист-раскрашиваемый. Однако сама теорема Грёча не распространяется от раскраски до раскраски списком: существуют планарные графы без треугольников, которые нельзя раскрашивать по трем спискам.[3] В 1989 году Ричард Стейнберг и Дэн Янгер[4] дал первое правильное доказательство на английском языке двойственной версии этой теоремы. В 2012 году Набиха Асгар[5] дал новое и гораздо более простое доказательство теоремы, вдохновленное работами Томассена.

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

Верен немного более общий результат: если планарный граф имеет не более трех треугольников, то он трехкратный.[1] Однако планарный полный график K4, и бесконечно много других плоских графов, содержащих K4, содержат четыре треугольника и не могут быть раскрашены тремя цветами. В 2009, Дворжак, Krá и Томас объявил доказательство другого обобщения, выдвинутого в 1969 г. Л. Гавелом: существует постоянная d такой, что если в плоском графе нет двух треугольников на расстоянии d друг друга, тогда это может быть цветной с тремя цветами.[6] Эта работа легла в основу выставки Дворжака 2015 года. Европейская премия по комбинаторике.[7]

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

Теорема не может быть обобщена на все плоские K4-свободные графы: не каждый планарный граф, требующий 4-х цветов, содержит K4. В частности, существует планарный граф без 4-циклов, который не может быть 3-цветным.[8]

Факторинг через гомоморфизм

3-раскраска графа грамм может быть описан гомоморфизм графов из грамм в треугольник K3. На языке гомоморфизмов теорема Грётша утверждает, что каждый плоский граф без треугольников имеет гомоморфизм в K3.Назераср показал, что любой плоский граф без треугольников также имеет гомоморфизм Граф Клебша, 4-хроматический граф. Объединив эти два результата, можно показать, что каждый планарный граф без треугольников имеет гомоморфизм в 3-раскрашиваемый граф без треугольников тензорное произведение из K3 с графом Клебша. Раскраска графа может быть восстановлена составление этот гомоморфизм с гомоморфизмом от этого тензорного произведения к его K3 фактор, но граф Клебша и его тензорное произведение с K3 оба неплоские; не существует плоского графа без треугольников, в который можно было бы отобразить любой другой плоский граф без треугольников с помощью гомоморфизма.[9]

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

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

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

Для плоского графа без треугольников можно найти 3-раскраску графа в линейное время.[10]

Примечания

  1. ^ а б Грюнбаум (1963).
  2. ^ Томассен (2003)
  3. ^ Глебов, Косточка и Ташкинов (2005).
  4. ^ Штейнберг и младший (1989)
  5. ^ Асгар (2012)
  6. ^ Дворжак, Зденек; Krá, Daniel; Томас, Робин (2009), Трехкратные графы без треугольников на поверхностях V. Раскрашивание плоских графов с удаленными аномалиями, arXiv:0911.0885, Bibcode:2009arXiv0911.0885D.
  7. ^ «Европейская премия по комбинаторике», Еврокомб 2015, Университет Бергена, сентябрь 2015 г., получено 2015-09-16.
  8. ^ Хекман (2007).
  9. ^ Насераср (2007), Теорема 11; Нешетржил и Оссона де Мендес (2012).
  10. ^ Дворжак, Каварабаяши и Томас (2009). Для более ранней работы над алгоритмами этой проблемы см. Ковалик (2010).

Рекомендации