Теорема о четырех цветах (4CT) гласит, что каждый планарный граф имеет четыре раскраски. Есть два доказательства, представленные [Аппель, Хакен 1976] и [Робертсон, Сандерс, Сеймур, Томас 1997]. Оба эти доказательства являются компьютерными и довольно пугающими.
Есть несколько гипотез в теории графов, которые подразумевают 4CT. Разрешение этих предположений, вероятно, требует лучшего понимания доказательств 4CT. Вот одна из таких гипотез:
Гипотеза : Пусть - плоский граф, пусть C - множество цветов, а f : C → C - свободная инволюция с фиксированной точкой. Пусть L = ( L v : v ∈ V ( G ) ) таково, что
- для всех v ∈ V и
- если , то F ( & alpha ; ) ∈ L V для всех об ∈ V , для всех альфа ∈ C .
Тогда существует -раскраска графа G .
Если вам известны такие предположения, подразумевающие 4CT, перечислите их по одному в каждом ответе. Я не смог найти исчерпывающий список таких догадок.
источник
Ответы:
4CT эквивалентно:
источник
Другая механическая проверка теоремы о 4 цветах была сделана Джорджем Гонтье из Microsoft Research Cambridge. Разница с его доказательством состоит в том, что вся теорема была сформулирована и механически проверена с использованием помощника по доказательству Coq, в то время как другие доказательства содержат только вычисления ядра, написанные на ассемблере и C, и, таким образом, могут быть ошибочными. Доказательство Гонтье охватывает как вычислительные, так и логические аспекты всего в 60 000 строк Coq.
источник
Я говорил об этом в своем блоге, и наше понимание таково: например, состояние Тейта может быть ослаблено, так как существует раскраска, в которой не более o (n) ошибок. Смотрите здесь: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/
источник
Посмотрите на Т. Саати, Тринадцать красочных вариаций четырехцветной гипотезы Гатри, Американская математика. Ежемесячно, 79 (1972) 2-43 для многих примеров.
Кроме того, в книге Дэвида Барнетта «Раскраска карты, многогранники и проблема четырех цветов», MAA, серия Dolciani, том 8, 1983, приводится много примеров. Один особенно интересный результат в книге Барнете таков: если всегда можно обрезать вершины выпуклого многогранника, чтобы получить трехвалентный выпуклый многогранник так, чтобы число сторон каждой грани было кратно трем, это подразумевает правда четырехцветной гипотезы.
источник
Гипотеза Хадвигера .
источник
В статье « Абсолютные плоские ретракты и четырехцветная гипотеза» Павол Ад доказал несколько эквивалентных формулировок для 4CT. Один из них гласит:
источник
Каждый кубический плоский план без мостов имеет 3-краевое окрашивание. (Это эквивалентно 4CT, из-за Тейта.)
источник
Статья Дрора Бар-Натана «Алгебры Ли и теорема о четырех цветах» (Combinatorica 17-1 (1997) 43-52, последнее обновление - октябрь 1999 г., arXiv: q-alg / 9606016 ) содержит привлекательное утверждение об алгебрах Ли, эквивалентное Теорема о четырех цветах. Понятия, фигурирующие в утверждении, появляются и в теории инвариантов конечного типа узлов (инвариантов Васильева) и 3-многообразий.
источник
Предложение 2.4 в этом документе http://www.sciencedirect.com/science/article/pii/0012365X9500109A# дает другую формулировку для 4CT.
источник
Описание высокого уровня автоматизированного доказательства, сделанное Гонтье, стоит прочитать, если вы ищете более глубокое понимание.
Юрий Матиясевич изучил несколько вероятностных переформулировок теоремы о четырех цветах, включающих положительные корреляции между двумя понятиями сходства между раскрасками. Его доказательства эквивалентности опираются на соответствующий многочлен графа, который обеспечивает другой вероятный указатель на гипотезы, которые подразумевают теорему.
источник
Я только что прочитал в статье Чалопина и Гонсалвеса (STOC '09) следующую гипотезу Запада:
Поскольку параллельные сегменты образуют независимое множество в таком представлении, эта гипотеза подразумевает 4CT, но, возможно, даже сильнее.
Ссылка: Запад, Открытые проблемы . SIAM J Discrete Math Newsletter, 2 (1): 10-12, 1991.
источник
Снарк является связным, bridgeless кубического графа , который не рёберный 3-раскраски. Следуя википедии, догадка о догадках , обобщающая 4CT, выглядит следующим образом:
Опять же, согласно википедии, доказательство этой гипотезы было объявлено в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом.
источник
«Маркировка лица максимальных плоских графов» - это название моей старой статьи, недавно опубликованной, в которой я преобразовал 4 раскраски максимальных плоских графов в последовательность маркировки граней. Ссылка на статью http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf
источник
Как
Л. Х. Кауфман, Переформулировка теоремы о цвете отображения , Дискретная математика 302 (2005) 145–172
указывает на то, что принцип Примальности, обусловленный Г. Спенсером-Брауном, а также гипотеза Элиахо-Крючкова являются эквивалентными переформулировками ПКТ.
источник
Статья Гарри Боулина и Мэтью Дж. Брина «Раскраска плоских графиков с помощью цветных контуров в ассоциаэдрах», последняя редакция 12 мая 2013 года, arXiv: 1301.3984 math.CO, содержит следующую гипотезу на странице 26:
Утверждается, что гипотеза 6.4, вытекающая из предыдущих положений и теорем в статье, эквивалентна 4CT.
источник
К -потоку на неориентированном графе G представляет собой ориентированный граф , полученный путем замены каждого ребра в G с дугой и присвоением ему целое числа между -k и к , исключительным, таким , что для каждой вершины в G, сумма целых чисел назначенный дугам, указывающим на эту вершину, равен сумме целых чисел, назначенных дугам, указывающим. NWZ (нигде ноль) k- поток - это k- поток, в котором ни одной дуге не был присвоен номер 0.
Для любого плоского графа G двойство G - это граф, который содержит одну вершину для каждой грани в плоском вложении G , и две вершины в двойственном числе делят одно ребро, соединяя их для каждого ребра, которое соответствующие грани в G разделяют между ними в их границах. Согласно TUTTE в Flow-раскраска теорему двойственности, плоский граф, без перешейка (т.е. краев которого удаление приведет к увеличению числа компонентов) имеет NWZ к -потоку тогда и только тогда , когда его сопряженный к -colourable. Другими словами, планарный граф является 4-цветным тогда и только тогда, когда его двойственный имеет 4-поток NWZ.
Обратите внимание, что 4CT требует, чтобы у рассматриваемого плоского графа не было петель (ребер, соединяющих любую вершину с самим собой), потому что любой граф с петлей не может быть окрашен в вершины с любым набором цветов, поскольку любая вершина с петлей была бы смежной с вершины одного цвета, независимо от их цвета.
источник
Я работаю над этим:
Если вы можете доказать теорему для прямоугольных карт, которые являются картами, сделанными из перекрывающихся листов бумаги, вы также доказали 4ct. Кроме того, в поиске могут рассматриваться только карты с гранями, имеющими все 5 или более ребер.
Смотрите http://4coloring.wordpress.com/ для деталей.
источник