Оглавление
Введение
1. Общая характеристика работы .
2. Основные понятия и обозначения
3. Обзор результатов диссертации
1. Младшие вершины и ребра в плоских графах
1.1. Теоремы о весе ребра в плоском графе
1.2. Доказательство верхних оценок из теоремы 1.4
1.3. Неулучшаемость оценок из теоремы 1.4 .
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.2.
3.3. Переход к подграфу без разделяющих циклов длины 4 и 5.
3.4. Свойства слабых 5граней .
3.5. Применение формулы Эйлера.
4. Минимальные 2дистанционные степени и рхромати
ческие числа плоских графов.
4.1. Обзор полученных результатов и формулировка структурной теоремы
4.2. Доказательство теоремы о триангуляциях
4.2.1. Правила перераспределения зарядов .
4.2.2. Правило усреднения
4.2.3. Предпучки и разделители
4.2.4. Строение окрестности 5вершины.
4.3. Доказательство общей структурной теоремы
4.3.1. Лемма о добавлении ребра.
4.3.2. Триангулирование минимального контрпримера
4.4. Следствия для 2дистанционных степеней и р. 7раскрасок .
4.4.1. Верхние оценки для минимальной 2дистатщонной степени вершин плоского графа .
4.4.2. Верхние оценки для р, хроматических чисел плоских графов .
5. Оценки для числа вырожденности графов пересечений боксов на плоскости
5.1. Семейства плоских боксов и связанные с ними понятия
5.2. Доказательство теоремы о числе вырожденности 5графов.
Литература
- Київ+380960830922