Структурные свойства и раскраски плоских графов

• Автор: Глебов, Алексей Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Новосибирск
• Количество страниц: 129 с. : ил

Оглавление
Введение

1. Общая характеристика работы

2. Основные понятия и обозначения

3. Обзор результатов диссертации

1. Младшие вершины и ребра в плоских графах

1.1. Теоремы о весе ребра в плоском графе

1.2. Доказательство верхних оценок из теоремы 1.

1.3. Неулучшаемость оценок из теоремы 1.

2. Разложение плоского графа обхвата 5 на пустой и ациклический подграфы

2.1. Раложения графов на вырожденные подграфы

2.2. Теорема о продолжении (1, 2)~раскраски
2.3. Свойства минимального контрпримера к теореме о продолжении
(1,2)-раскраски
2.4. Слабые 5-грани и их свойства
2.5. Применение формулы Эйлера
3. Продолжение 3-раскраски с двух вершин в плоском графе без 3-циклов
3.1. Теорема о продолжении 3-раскраски
3.2. Свойства контрпримера к теореме 3.
3.3. Переход к подграфу без разделяющих циклов длины 4 и
3.4. Свойства слабых 5-граней
3.5. Применение формулы Эйлера

4. Минимальные 2-дистанционные степени и (р,ц)-хромати-ческие числа плоских графов
4.1. Обзор полученных результатов и формулировка структурной теоремы
4.2. Доказательство теоремы о триангуляциях
4.2.1. Правила перераспределения зарядов
4.2.2. Правило усреднения
4.2.3. Предпучки и разделители
4.2.4. Строение окрестности В-вергаины
4.3. Доказательство общей структурной теоремы
4.3.1. Лемма о добавлении ребра
4.3.2. Триангулирование минимального контрпримера
4.4. Следствия для 2-дистанционных степеней и (р, д)-раскрасок
4.4.1. Верхние оценки для минимальной 2-дистанционной степени вершин плоского графа
4.4.2. Верхние оценки для (р, ^-хроматических чисел плоских графов
5. Оценки для числа вырожденности графов пересечений боксов на плоскости
5.1. Семейства плоских боксов и связанные с ними понятия
5.2. Доказательство теоремы о числе вырожденности Д-графов
Литература

Введение
1. Общая характеристика работы
В настоящей работе решается ряд задач о локальном строении и раскрасках плоских графов. Известно, что ключом к решению многих задач о раскрасках является применение подходящих структурных результатов. Наиболее ярким примером в этом отношении служит полученное в 1976 г. К. Аппелем и В. Хакеном [13, 14, 15] доказательство теоремы о четырех красках, основанное на построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другой пример того же рода — это построенная О. В. Бородиным [5, 17, 19] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную ракскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, — ациклический).
В настоящей работе подобный подход находит свое применение в главе 4 при получении верхних оценок для (р, дихроматических и 2-дистанционных хроматических чисел плоских графов (теоремы 4.4 и 4.5). При доказательстве теорем 4.4 и 4.5 используется неизбежная система сводимых конфигураций, наличие которой обеспечивается доказанной до этого структурной теоремой 4.1. Результат теоремы 4.1 также используется при доказательстве точных верхних оценок для минимальных степеней вершин в квадрате плоского графа (теорема 4.3).
Недостатком описанного подхода по применению структурных результатов при доказательстве теорем о раскрасках является то, что возникающие системы конфигураций часто оказываются громоздкими и не представляют интереса вне контекста той задачи о раскраске, для решения которой они используются. Начиная со второй половины 20 века в работах таких математиков как А. Лебег [43], А. Коциг [40, 41, 42], Б. Грюнбаум [28, 29, 30), Е. Юцович [35, 36], О. В. Бородин [3, 6, 7, 8, 9, 12, 18, 19, 21, 22] и других теоремы о локальном строении плоских графов (а также графов, вложенных в другие поверхности) начинают выступать в качестве самостоятельного объекта изучения, важного с точки зрения расшифровки структуры плоских графов. В связи с этим особое значение приобретает доказательство неулучшаемых структурных результатов.
В неулучшаемой структурной теореме выделяется такая минимальная система неизбежных фрагментов, что каждый фрагмент характеризуется набором числовых параметров, налагающих ограничения на различные характеристики плоского графа (такие как степени вершин, ранги граней, веса ребер и граней и др.). Минимальность системы означает, что при отбрасывании любого фрагмента или при уменьшении любого из параметров хотя бы на единицу теорема перестает быть верной.

две различные граничные вершины и содержащую хотя бы одну внутреннюю вершину графа Д (рис. 2.1, а). Если а и Ь — две различные внутренние вершины в Д, то проективной а-Ъ-цепью назовем любую пару простых цепей аа... ат и ЪЪ±... Ъп, где вершины ат и Ьп являются граничными в Д (рис. 2.1, б). Под обобщенным циклом
Рис. 2.
(обобщенной а-Ь-цепью) условимся понимать обычный цикл (а-6-цепь) или проективный цикл (проективную а-Дцепь) в С?.
Теорема 2.2. Пусть Д — такой связный плоский граф, что у(Д) ^ 5 и 5 ^ г(/0) ^ 8. Тогда любая допустимая предраскраска (р граничного цикла Со может быть продолжена до (1,2)-раскраски ф графа С таким образом, что в Є отсутствуют обобщенные циклы, состоящие из вершин цвета 2.
Замечание 2.2. Последнее свойство раскраски ф можно сформулировать следующим образом: любые две вершины, окрашенные цветом 2 в предраскраске ір и принадлежащие различным компонентам связности в графе Ср~1{2)], принадлежат различным компонентам и в графе С[ф~1{2)}.
Замечание 2.3. Далее в этой главе будем называть просто раскраской любую
(1,2)-раскраску вершин плоского графа, для которой выполнено утверждение теоремы 2.2.
Вывод теоремы 2.1 из теоремы 2.2. Достаточно доказать теорему 2.1 в случае, когда граф С связен. В начале предположим, что в С имеется грань / ранга от 5 до 8. Не уменьшая общности, грань / можно считать внешней, т. е. / = /0. Из условия 5(6?) ^ 5 следует, что граничный цикл Со грани /о содержит не более одной хорды (что возможно лишь при г (/о) = 8). Это означает, что на множестве вершин цикла До может быть задана допустимая предраскраска <р, которая согласно теореме 2.2 продолжается до некоторой (1,2)-раскраски вершин графа Д.
Если в графе Д отсутствуют грани ранга от 5 до 8, то выберем любую вершину х € И(Д) и добавим к Д новые вершины хі,х<2,хз, Хі и ребра хх, Х%2, хухъ, Х3Х4, Х4Х так, что в полученном плоском графе Єї цикл (т,хг,ащтД ограничивает некоторую 5-грань /. Далее применим предыдущие рассуждения.