- •Типы графов
- •Маршруты и связность
- •Степени
- •Задача Рамсея
- •Экстремальные графы
- •Графы пересечений
- •Операции над графами
- •Графы блоков и точек сочленения
- •Точки сочленения, мосты и блоки
- •Деревья
- •Описание деревьев
- •Центры и центроиды
- •Деревья блоков и точек сочленения
- •Независимые циклы и коциклы
- •Матроиды
- •Обходы графов
- •Эйлеровы графы
- •Гамильтоновы графы
- •Реберные графы
- •Некоторые свойства реберных графов
- •Характеризация реберных графов
- •Специальные реберные графы
- •Реберные графы и обходы
- •Тотальные графы
- •Раскраски
- •Хроматическое число
- •Теорема о пяти красках
- •Гипотеза четырех красок
- •Однозначно раскрашиваемые графы
- •Критические графы
- •Гомоморфизмы
- •Хроматический многочлен
- •Матрицы
- •Матрица смежностей
- •Матрица инциденций
- •Матрица циклов
- •Обзор дополнительных свойств матроидов
- •Связность
- •Связность и реберная связность
- •Орграфы
- •Орграфы и соединимость
- •Ориентированная двойственность и бесконтурные орграфы
- •Орграфы и матрицы
- •Турниры
- •Обзор по проблеме востановления турниров
- •Волновой алгоритм
- •Алгоритм Дейкстры
- •Алгоритм Флойда
- •Алгоритм Йена
- •Алгоритм Краскала
Однозначно раскрашиваемые графы
Пусть G — помеченный граф. Каждая его хr(G)-раскраска порождает разбиение множества его вершин на хr(G) одноцветных классов. Если xr(G) = n и каждая
n-раскраска графа G порождает одно и то же разбиение множества V, то G называется однозначно n-раскрашиваемым, или простооднозначно раскрашиваемым.
Граф, представленный на рисунке , однозначно 3-раскрашиваем, так как каждая его 3-раскраска дает разбиение {u1}, {u2, u4}, {и3, и5}. Пятиугольник не однозначно 3-раскрашиваем: возможны пять различных разбиений множества его вершин. Начнем с элементарных замечаний, касающихся однозначно раскрашиваемых графов. Прежде всего, в любой n-раскраске однозначно n-раскрашиваемого графа G каждая вершина v смежна, по крайней мере с одной вершиной каждого цвета, отличного от цвета, приписанного v. Иначе можно было бы получить другую n-раскраску графа G, перекрасив вершину v. Отсюда следует, что (G)>n -1. Необходимое условие однозначной раскрашиваемости графа найдено Картрайтом и Харари .
Теорема.В n-раскраске однозначно n-раскрашиваемого графа подграф, порожденный объединением любых двух одноцветных классов, связен.
Из теоремы следует, что каждый однозначно n-раскрашиваемый граф связен. Чартрэнд и Геллер получили более сильный результат:
Теорема.Каждый однозначно n-раскрашиваемый граф (n - 1)-связен.
Поскольку объединение любых k одноцветных классов однозначно
n-раскрашиваемого графа, 2>n, порождает однозначно n-раскрашиваемый граф, то из теоремы вытекает
Следствие(а).В каждой n-раскраске однозначно n-раскрашиваемого графа подграф, порожденный объединением любых k одноцветных классов,
2<k<n, (k - 1) -связен.
Легко привести примеры 3-хроматических графов, не содержащих треугольников. Действительно, в теореме говорится, что для любого n существуют n-хроматические графы, не содержащие треугольников и, следовательно, не имеющие подграфов, изоморфных Кn. Харари, Хедетниеми и Робинсон получили более сильный результат:
Теорема.Для каждого n>3 существует однозначно
n-раскрашиваемый граф, не содержащий подграфов, изоморфных Кn.
Граф G, приведенный на рисунке, иллюстрирует теорему для случая n=3.
Естественно, граф однозначно 1-раскрашиваем тогда и только тогда, когда он
1-раскрашиваем, т. е. вполне несвязен. Хорошо известно, что граф G однозначно 2-раскрашиваем тогда и только тогда, когда он 2-хроматический и связный.
Как и можно было ожидать, об однозначно n-раскрашиваемых графах, n>З, известно мало. Для планарных графов сведений больше, но в силу теоремы о пяти красках достаточно рассматривать только значения 3<n<5. Результаты в этом направлении принадлежат Чартрэнду и Геллеру.
Теорема.Пусть G есть 3-хроматичвский плоский граф. Если G содержит такой треугольник Т, что для любой вершины v графа G существует последовательность Т1,Т2,Т3, ...., Тt треугольников, в которой соседние
два имеют общее ребро и v Тt, то G — однозначно 3-раскрашиваемый граф.
Из этой теоремы немедленно вытекает
Следствие(а).Если двусвязный 3-хроматический плоский граф G имеет не более одной области, не являющейся треугольником, то G — однозначно 3-раскрашиваемый граф.
Предложение, обратное следствию (а), не верно: однозначно
3-раскрашиваемый пленарный граф может иметь более одной области, не являющейся треугольником (рис.). Однако каждый однозначно
3-раскрашиваемый пленарный граф должен содержать треугольники.
Теорема.Однозначно 3-раскрашиваемый планарный граф,
имеющий не менее 4 вершин, содержит, по крайней мере два треугольника.
В случае однозначно 4-раскрашиваемых пленарных графов ситуация особенно проста.
Теорема.Каждый однозначно 4-раскрашиваемый планарный граф является максимальным планарным графом.
Хотя вопрос существования 5-раскрашиваемых пленарных графов остается все еще открытым, результат Хедетниеми, приведенный в работе Чартрэнда и Геллера, разрешает проблему однозначно 5-раскрашиваемости.
Теорема.Ни один из планарных графов не является однозначно 5-раскрашиваемым.