Некоторые аспекты правильных раскрасок графов

• Автор: Гравин, Николай Вадимович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Санкт-Петербург
• Количество страниц: 84 с. : ил.

Оглавление
1 Введение
1.1 Определения
1.1.1 Базовые понятия
1.1.2 Понятия, связанные с раскрасками
1.2 Результаты диссертации
2 Динамические Раскраски и Гиперграфы
2.1 Верхние оценки на хроматическое число гиперграфов
2.2 Доказательство теоремы 2.
3 Теорема Брукса и Динамические Раскраски
3.1 (с, р)-невырожденность
3.2 Доказательство теоремы 3.
3.2.1 Доказательство теоремы 3.
3.2.2 Доказательство леммы 3.
4 Алгоритмические Аспекты в Теореме Брукса
4.1 Формальная постановка задачи
4.1.1 Условие связности

ОГЛАВЛЕНИЕ
4.1.2 Основной результат
4.2 Задала списочной е?-раскраски
4.2.1 Алгоритм
4.2.2 Реализация процедур
4.2.3 Доказательство корректности алгоритма
4.2.4 Анализ сложности алгоритма
4.3 Конструктивное доказательство теоремы Брукса
Глава
Введение
Теория графов является одним из важнейших и интереснейших разделов математики. Помимо многочисленных приложений в различных областях математики, таких как теория вероятностей, комбинаторика, алгебра и топология, она является краеугольным камнем в современной информатике, как теоретической, так и прикладной. В любом учебнике по алгоритмам едва ли не треть всего материала будет посвящена алгоритмам на графах. Терминология теоретической информатики немыслима без использования понятий теории графов, как-то дерево, вершина, ребро, путь, цикл и более сложных, таких как экспандер.
Правильные раскраски графов на сегодняшний день представляются, вероятно, одной из самых популярных и интенсивно изучаемых тем в теории графов. Как наиболее яркие примеры результатов в данной области стоит отметить классификацию совершенных графов и проблему раскрашиваемое плоского графа в четыре цвета. Непосредственно связаны с раскрасками хроматический полином и полином Татта, изучению свойств

ГЛАВА 3. ТЕОРЕМА БРУКСА И ДИНАМИЧЕСКИЕ РАСКРАСКИ
- полный граф. В силу произвольности выбора ?;і и г>2 и того, что граф Ст(у{С) и У{С2)) ~ клика размера а* + щ + 1 в С?у, мы получаем, что вершины из множества У (Сі) и V(Сі) не смежны с другими вершинами г-ых и у-ых цветов.
2) Если же мы вернулись в результате перекрашиваний к клике С/, то исходя из всего выше сказанного (мы можем считать, что мы начали процесс перекрашивания с ф) С(У(С/) и У(С/+і)) — клика в графе С?. А тогда мы получаем 1 = 1, так как вершины из множества У (С/) и У(Сі+) не смежны с другими вершинами г-ого и .7-ого цвета.

Замечание 3.2. Отметим, что в доказательстве утвероіедения З.бмы существенно пользовались тем, что > 2 и с^- > 2. Иначе мы просто не смогли бы выбрать отличную от всех гу вершину.
Утверждение 3.7. В любой раскраске дс Є П нет, больших клик.
Доказательство. Пусть у этой раскраски есть большая клика С. например, первого цвета. Применим утвероіедение 3.6 к первому и второму цветам. Получим полный граф на вершинах цвета 1 и 2 размера оц + ао + 1 содержащий С. Заметим, что мы можем произвольным образом разбить этот полный граф на две части цвета 1 и 2 размера оц + 1 и а2 соответственно, при этом полученная новая раскраска все равно будет лежать в П. Используя утверждение 3.6 для первого и г-ого цвета (г Є [2, с + 1]) и предыдущее соображение легко доказать наличие в графе С полного под-

графа на 1 -Ь 53 аі вершине, то есть полного подграфа размера О + 1 -.7=
противоречие с условием теоремы 3.1. □