Ориентированная и 2-дистанционная раскраски плоских графов с заданным обхватом

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

1. Общая характеристика работы
2. Основные понятия и обозначения
3. Обзор результатов диссертации
1. Ориентированные раскраски
1.1. Обзор и обсуждение результатов главы
1.2. Связь с круговыми раскрасками и алгебраическими потоками
1.3. Доказательство теоремы 1
1.3.1. Свойства гомоморфизмов в С(5; 1,2)
1.3.2. Основные структурные свойства минимального контрпримера
1.3.3. Завершение доказательства теоремы
1.4. Доказательство теоремы 1
1.4.1. Структурные свойства минимального контрпримера
1.4.2. Завершение доказательства теоремы
1.5. Доказательство теоремы 1
1.5.1. Свойства гомоморфизмов в Р(47)
1.5.2. Структурные свойства минимального контрпримера
1.5.3. Завершение доказательства теоремы
2. 2-дистанционная раскраска
2.1. Обзор и обсуждение результатов главы
2.2. Доказательство теоремы 2
2.2.1. Случай Д(О)
2.2.2. Случай д
2.3. Доказательство теоремы 2
2.3.1. Структурные свойства минимального контрпримера
2.3.2. Завершение доказательства теоремы
Литература

1. Общая характеристика работы
Раскраска графа в широком смысле есть разбиение дискретного объекта на более простые подобъекты. Ввиду своей общности теория раскраски занимает в дискретной математике центральное положение и имеет многочисленные приложения, особенно в информатике (распределение памяти, диагностика ошибок в программах и т. д.), задаче назначения частот в мобильном телефонировании, в теории расписаний и др. Гомоморфизмы графов - более общее понятие, чем раскраска (действительно, задача классической вершинной раскраски есть не что иное, как гомоморфизм на полный граф), и в последнее время они интенсивно изучаются в самых разных аспектах.
Раскраска плоских графов также представляет собой широкую область исследования, выросшую из знаменитой проблемы четырех красок, решенной в 197G г. К. Аппелем и В. Хакеном [2, 3, 4], и в которой в настоящее время работают сотни специалистов.
Доказательство теоремы о четырех красках основано на построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другой пример того же рода — это построенная О.В. Бородиным (46, 5] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную ракскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, —- ациклический). Теорема О.В. Бородина об ациклической 5-раскраске включена во введении книги В.Тофта и Т. Йенсена [22] в число 40 важнейших результатов по раскраске графов за все годы. В последнее время в работах зарубежных математиков эта теорема получила ряд приложений к другим задачам раскраски. В главе "Плоские графы"этой книги цитируются более 20 результатов О.В. Бородина, A.B. Косточки, В.А. Аксенова и JI.C. Мельникова. Коллектив лаборатории теории графов Института математики СО РАН является одним из мировых лидеров именно в области раскраски плоских графов.
В диссертации изучаются ориентированная и 2-дистанционная раскраски разреженных плоских графов. В теории графов мерой разреженности графа G принято считать максимальную среднюю степень вершин, mad(G), всех его подграфов. Для плоских же графов разреженность обычно выражают в терминах обхвата g(G), т. е. длины минимального цикла. Нетрудно показать, что если граф G плоский, то mad(G) < ■ С другой стороны, в силу известной теоремы Эрдеша [14] о раскраске случайных графов, существует (неплоский) граф G, имеющий произвольно

большие д(0) и тас1{0). Часть результатов диссертации доказывается для произвольных разреженных графов, т. е. с использованием максимальной средней степени, а не обхвата.
Рассматриваемые в диссертации виды раскрасок занимают в теории графов заметное место. Первый из них исследуется с конца 70-х годов, а второй — с начала 90-х. Оба вида раскрасок привлекают интерес специалистов по теории графов как своей математической красотой, так и связями с другими видами раскрасок (ациклической, круговой, тотальной, реберной, (р, ^-раскраской и предписанной) и алгебраической теорией потоков.
Ориентированные раскраски сводятся к построению гомоморфизма широких классов ориентированных графов на специально подобранные орграфы (мишени) с небольшим числом вершин. Отметим, что классическая задача вершинной раскраски может рассматриваться как построение гомоморфизма заданного графа на наименьший полный граф Кп. Ориентированная раскраска иногда оказывается тесно связанной с другой задачей о гомоморфизме, круговой раскраской, в которой ищется гомоморфизм неориентированных графов на минимальный циркулянт. Другими словами, требуется раскрасить вершины заданного графа числами 0,1 к -1 так, чтобы цвета любых соседних вершин отличались на величину, ограниченную как снизу, так и сверху. Отметим, что в классической раскраске вершин ограничение сверху на расстояние между цветами соседних вершин отсутствует, а снизу равно 1, в то время как в (р, 0)-раскраске ограничение снизу равно р, а ограничение сверху также отсутствует.
За пределами теории графов интерес к 2-дистанционной раскраске объясняется тем, что и она сама и такие ее обобщения как (р, д)-раскраска и предписанная (р, Цель диссертационной работы состоит в получении новых результатов о раскрасках (ориентированных и 2-дистанционных) разреженных графов, в основном плоских, а также вспомогательных результатов о строении таких графов.
Работа носит теоретический характер; полученные результаты о 2-дистанционных раскрасках плоских графов имеют отношение к задачам, возникающим в мо-

Глава
2-дистанционная раскраска
2.1. Обзор и обсуждение результатов главы
Напомним, что раскраска / : Т(<7) -)• {1,2 к} графа (7 называется 2дистанционной, если любые две вершины, находящиеся на расстоянии не более 2, окрашены в различные цвета. Наименьшее число цветов в 2-дистанционных раскрасках графа Є называется 2-дистанционным хроматическим числом графа (7 и обозначается через Х2(<3).
В теории графов известна гипотеза Г. Вегнера [44] о том, что Хг( 8. Пример плоского мультиграфа, построенного К. Шенноном [37], показывает, что если верхняя оценка в гипотезе Вегнера верна, то она достижима. Наилучшей из опубликованных верхних оценок для произвольных плоских графов является ^ [|Д] +1 при Д > 47 ([48]).
Очевидно, что Хг(<3) > Д+1 для любого графа Є (ввиду того, что в любом графе есть звезда Лдд). Возникает вопрос: для каких графов 2-дистанционное хроматическое число равно этой тривиальной нижней оценке? К таким графам относятся, например, все деревья.
Легко видеть, что при А = 2 существуют графы с хг = 4 и произвольно большим обхватом, например, Сзк+г В [56, 49] нами показано, что при Д((7) ^ 3, если плоский граф б разрежен, т. е. его обхват при фиксированном Д достаточно велик, то Х2( Теорема 2.1. Пусть (7 — планарный граф. Тогда хг((?) = Д + 1 в каждом из следующих случаев:
(і) А = 3 и д > 24;
(и) Д ^ 15 и д
Здесь напомним, что к-репъ содержит ровно к вершин степени 2, а под (к к^)-вершиной понимается (/-вершина, инцидентная с/ различным цепям, где г-я цепь (1 ^ г < (1) содержит не менее кі вершин степени 2. Доказательство случая (і) основано на том, что в минимальном контрпримере нет: > 6 цепей, (5, 4, 1)-, (5, 3,2)-, (4, 4, 2)-, (4, 3, 3)-вершин, а также смежных (5,5,0)- и (5,4,0)-вершин.
В случае (й) описать строение минимального контрпримера труднее.