Теорема о пяти красках
Хотя не известно, все ли планарные графы 4-раскрашиваемы, все они, несомненно, 5-раскрашиваемы. Мы приведем доказательство этого известного утверждения, принадлежащее Хивуду.
Теорема.Каждый планарный граф 5-раскрашиваем.
Доказательство. Будем доказывать индукцией по числу р вершин. Для любого планарного графа с р<5 вершинами результат тривиален, поскольку такой граф р-раскрашиваем.
Допустим, что все планарные графы с р вершинами (р>= 5) 5-раскрашиваемы. Пусть G — плоский граф с р+1 вершинами. В силу следствия в графе G найдется вершина v степени 5 или менее. По предположению индукции плоский граф G - v 5-раскрашиваем.
Рассмотрим приписывание цветов вершинам графа G — v, при котором получается 5-раскраска; цвета будем обозначать через ci, l<ci<5. Ясно, что если некоторый цвет, скажемcj, не используется в раскраске вершин, смежных сu, то, приписав цвет сj вершине v, получим 5-раскраску графа G.
Осталось рассмотреть случай, когда deg v = 5 и для вершин графа G, смежных с v, используются все пять цветов. Переставим номера цветов, если это необходимо, так, чтобы вершины, смежные с v и окрашенные в цвета c1, с2, с3, с4, с5, были циклически упорядочены. Пометим теперь вершину, смежную с v окрашенную цветом ci, буквой vi, l<i<5
Обозначим через G13 подграф графа G — v, порожденный всеми вершинами, окрашенными в один из цветов с1 и с3. Если вершины v1 и v3 принадлежат различным компонентам графа G13, то 5-раскраску графа G - v можно получить, поменяв друг с другом (c1 на с3 и обратно)
цвета вершин той компоненты графа G13, которая содержит их. В этой 5-раскраске уже нет вершин, смежных с v и окрашенных в цветc1; поэтому, окрасив v в цвет с1, образуем 5-раскраску графа G. Если же вершины v1 и v3 принадлежат одной и той же компоненте графа G13, то в G между v1 и v3 существует простая цепь, все вершины которой окрашены в цвета с1 и с3. Эта цепь вместе с цепью v1v3 образует простой цикл, который обязательно окружает или вершину v2, или вершины v4 и у5. В любом из этих случаев v2 и v4 нельзя соединить простой цепью, все вершины которой окрашены в цвета с2 и с4. Следовательно, рассматривая подграф G24 графа G - v, порожденный всеми вершинами, окрашенными в цвета с2 и с4, заключаем, что вершины v2 и v4 принадлежат различным его компонентам. Таким образом, если поменять между собой цвета вершин в компоненте подграфа G24, содержащей v2, получим 5-раскраску графа G - v, и в ней ни одна из вершин, смежных с v, не будет окрашена в цвет с2. Поэтому, окрасив вершину v в цвет с2, образуем 5-раскраску всего графа G.
- Типы графов
- Маршруты и связность
- Степени
- Задача Рамсея
- Экстремальные графы
- Графы пересечений
- Операции над графами
- Графы блоков и точек сочленения
- Точки сочленения, мосты и блоки
- Деревья
- Описание деревьев
- Центры и центроиды
- Деревья блоков и точек сочленения
- Независимые циклы и коциклы
- Матроиды
- Обходы графов
- Эйлеровы графы
- Гамильтоновы графы
- Реберные графы
- Некоторые свойства реберных графов
- Характеризация реберных графов
- Специальные реберные графы
- Реберные графы и обходы
- Тотальные графы
- Раскраски
- Хроматическое число
- Теорема о пяти красках
- Гипотеза четырех красок
- Однозначно раскрашиваемые графы
- Критические графы
- Гомоморфизмы
- Хроматический многочлен
- Матрицы
- Матрица смежностей
- Матрица инциденций
- Матрица циклов
- Обзор дополнительных свойств матроидов
- Связность
- Связность и реберная связность
- Орграфы
- Орграфы и соединимость
- Ориентированная двойственность и бесконтурные орграфы
- Орграфы и матрицы
- Турниры
- Обзор по проблеме востановления турниров
- Волновой алгоритм
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Йена
- Алгоритм Краскала