В математической области теории графов , теорема Грётши является утверждение о том , что каждый треугольнике свободного плоского граф может быть окрашен только три цвета. Согласно теореме о четырех цветах , каждый граф, который можно нарисовать на плоскости без пересечения ребер, может иметь свои вершины, окрашенные не более чем в четыре разных цвета, так что два конца каждого ребра имеют разные цвета, но согласно теореме Грётша только три цвета нужны для плоских графов, не содержащих трех взаимно смежных вершин.
История
Теорема названа в честь немецкого математика Герберта Грётча , который опубликовал её доказательство в 1959 году. Первоначальное доказательство Грётша было сложным. Берге (1960) попытался упростить его, но его доказательство было ошибочным. [1]
В 2003 году Карстен Томассен [2] вывел альтернативное доказательство из другой связанной теоремы: каждый плоский граф с обхватом не менее пяти можно раскрашивать по трем спискам . Однако сама теорема Грётша не распространяется от раскраски до раскраски списком: существуют планарные графы без треугольников, которые нельзя раскрашивать по трём спискам. [3] В 2012 году Набиха Асгар [4] представила новое и гораздо более простое доказательство теоремы, вдохновленное работой Томассена.
В 1989 году Ричард Стейнберг и Дэн Янгер [5] дали первое правильное доказательство на английском языке двойственной версии этой теоремы.
Более крупные классы графов
Верен немного более общий результат: если в плоском графе не более трех треугольников, то он 3-раскрашиваем. [1] Однако планарный полный граф K 4 и бесконечно много других плоских графов, содержащих K 4 , содержат четыре треугольника и не являются 3-раскрашиваемыми. В 2009 году Дворжак , Краень и Томас объявили о доказательстве другого обобщения, выдвинутого в 1969 году Л. Гавелом: существует константа d такая, что если в плоском графе нет двух треугольников на расстоянии d друг от друга, то он может быть раскрашенным в три цвета. [6] Эта работа легла в основу Европейской премии Дворжака по комбинаторике 2015 года . [7]
Теорема не может быть обобщена на все неплоские графы без треугольников: не каждый неплоский граф без треугольников является 3-раскрашиваемым. В частности, граф Грёча и граф Хватала - это графы без треугольников, требующие четырех цветов, а микельский - это преобразование графов, которое можно использовать для построения графов без треугольников, требующих сколь угодно большого количества цветов.
Теорема также не может быть обобщена на все планарные K 4 -свободные графы: не каждый планарный граф, требующий 4 цветов, содержит K 4 . В частности, существует планарный граф без 4-циклов, который не может быть 3-цветным. [8]
Факторинг через гомоморфизм
3-раскраска графа G может быть описан с помощью графа гомоморфизма из G в треугольник K 3 . На языке гомоморфизмов теорема Грётша утверждает, что каждый плоский граф без треугольников имеет гомоморфизм в K 3 . Назераср показал, что каждый плоский граф без треугольников также имеет гомоморфизм графу Клебша , 4-хроматический граф. Сочетание этих двух результатов, можно показать , что каждый треугольник свободной плоский граф имеет гомоморфизм на треугольник свободной 3-раскраску графа, то тензорное произведение из K 3 с графом Клебша. Затем раскраску графа можно восстановить, составив этот гомоморфизм с гомоморфизмом этого тензорного произведения на его фактор K 3 . Однако граф Клебша и его тензорное произведение с K 3 не являются плоскими; не существует плоского графа без треугольников, в который можно было бы отобразить любой другой плоский граф без треугольников с помощью гомоморфизма. [9]
Геометрическое представление
Результат де Кастро и др. (2002) сочетает в себе теорему Греча с гипотезой Scheinerman в о представлении плоских графов , как пересечения графиков из отрезков прямых . Они доказали, что каждый плоский граф без треугольников может быть представлен набором отрезков прямой с тремя наклонами, так что две вершины графа смежны тогда и только тогда, когда отрезки, представляющие их, пересекаются. Затем можно получить 3-раскраску графа, присвоив двум вершинам один и тот же цвет, если их линейные сегменты имеют одинаковый наклон.
Вычислительная сложность
Для плоского графа без треугольников можно найти 3-раскраску графа за линейное время . [10]
Заметки
- ^ а б Грюнбаум (1963) .
- ^ Thomassen (2003)
- ↑ Глебов, Косточка и Ташкинов (2005) .
- ^ Асгар (2012)
- ↑ Steinberg & Younger (1989).
- ^ Дворжак, Зденек ; Krá, Daniel; Томас, Робин (2009), Трехцветные графы без треугольников на поверхностях V. Раскрашивание плоских графов с удаленными аномалиями , arXiv : 0911.0885 , Bibcode : 2009arXiv0911.0885D.
- ^ «Европейская премия в комбинаторике» , EuroComb 2015 , Бергенский университет, сентябрь 2015 г. , данные получены 16 сентября 2015 г..
- ^ Хекман (2007) .
- ^ Naserasr (2007) , теорема 11; Нешетржил и Оссона де Мендес (2012) .
- ↑ Дворжак, Каварабаяши и Томас (2009) . Более раннюю работу над алгоритмами для этой проблемы см. Kowalik (2010) .
Рекомендации
- Асгар, Nabiha (2012), "Грётша теорема" (PDF) , Магистерская диссертация, Университет Ватерлоо , DOI : 10,13140 / RG.2.1.1326.9367.
- Берже, Клод (1960), "Проблемные цвета в теории графов", Publ. Inst. Статист. Univ. Париж , 9 : 123–160. Цитируется Грюнбаумом (1963) .CS1 maint: postscript ( ссылка )
- de Castro, N .; Cobos, FJ; Дана, JC; Маркеса, А. (2002), "Треугольник-свободные плоские графы в виде графиков сегмент пересечения" (PDF) , журнал графов алгоритмов и приложений , 6 (1): 7-26, DOI : 10,7155 / jgaa.00043 , МР 1898201.
- Дворжак, Зденек ; Каварабаяси, Кен-ичи ; Томас, Робин (2009), "Трехцветные плоские графы без треугольников за линейное время", Proc. Двадцатый ACM-SIAM симпозиум по дискретным алгоритмам (PDF) , С. 1176-1182,. Arxiv : 1302,5121 , Bibcode : 2013arXiv1302.5121D , архивируется от оригинала (PDF) на 2012-10-18 , извлекается 2013-02-22.
- Глебов, АН; Косточка, А В; Ташкинов, В.А. (2005), «Меньшие плоские графы без треугольников, которые нельзя раскрашивать по трем спискам», Дискретная математика , 290 (2–3): 269–274, doi : 10.1016 / j.disc.2004.10.015.
- Стейнберг, Ричард; Янгер Д.Х. (1989), "Теорема Грётша для проективной плоскости", Ars Combinatoria , 28 : 15–31.
- Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Рейхе , 8 : 109–120, MR 0116320.
- Грюнбаум, Бранко (1963), "Теорема Грётча о 3-раскрасках", Michigan Math. J. , 10 (3): 303-310, DOI : 10,1307 / MMJ / 1028998916 , МР 0154274.
- Хекман, Кристофер Карл (2007), Прогресс в гипотезе Стейнберга , заархивировано из оригинала 22 июля 2012 г. , извлечено 27 июля 2012 г..
- Kowalik, Лукаш (2010), "Fast 3-раскраски треугольные свободной планарные графы" (PDF) , Algorithmica , 58 (3): 770-789, DOI : 10.1007 / s00453-009-9295-2.
- Naserasr, Реза (2007), "Гомоморфизмы и краевая-раскраска плоских графов", Журнал комбинаторной теории , Series B, 97 (3): 394-400, DOI : 10.1016 / j.jctb.2006.07.001 , MR 2305893.
- Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «2.5 гомоморфизм двойственности», разреженность , алгоритмы и комбинаторика, 28 , Гейдельберг: Спрингер, стр. 15–16, DOI : 10.1007 / 978-3-642-27875-4 , hdl : 10338 .dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
- Томассен, Карстен (2003), «Цветное доказательство краткого списка теоремы Грётча», Журнал комбинаторной теории, серия B , 88 (1): 189–192, DOI : 10.1016 / S0095-8956 (03) 00029-7.