Решетки разбиений натуральных чисел и хроматическая определяемость графов

• Автор: Королева, Татьяна Александровна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Екатеринбург
• Количество страниц: 133 с. : ил.

1 Решетка разбиений натуральных чисел

1 Предварительные сведения

2 Решетки МРЬ(п)

3 Решетка 7V.PL

2 Хроматическая определяемость атомов в решетках полных многодольных графов

4 Хроматические инварианты

5 Атомы в решетках полных многодольных графов

3 Хроматическая определяемость некоторых полных трехдольных графов

6 Хроматическая определяемость некоторых

полных трехдольных графов при г

7 Хроматическая определяемость некоторых

полных трехдольных графов при г
8 Хроматическая определяемость некоторых
полных трехдольных графов при г
Литература

Одна из наиболее известных задач теории графов — проблема четырех красок. Имеются сведения, что Мёбиус был знаком с этой проблемой в 1840 г., и достоверно известно, что Гутри сообщал де Моргану о данной проблеме в 1850 г. Первое из многих ошибочных доказательств было дано Кемпе [1] в 1879 г. Ошибку в доказательстве Кемпе в 1890 г. обнаружил Хивуд [2], который тогда же установил, что гипотеза верна, если "четыре” заменить на ’’пять”. Иными словами, Хивуд доказал, что любой планарный граф раскрашивается в пять красок.
В 1969 г. проблема четырех красок была сведена X. Хе-ли к рассмотрению весьма большого конечного числа случаев. Наконец, в 1976 г. Аппелль и Хейкен решили проблему четырех красок, но, возможно, не самым лучшим способом. Решение потребовало длительного перебора компьютером огромного числа случаев. Сам факт компьютерного решения проблемы четырех красок является, несомненно, выдающимся достижением, которое вполне достаточно для прекращения поиска контрпримера.
Более чем столетняя история попыток решения этой проблемы сыграла положительную роль в развитии различных разделов теории графов и особенно для исследования свойств раскрасок графов. Во многих работах было показано важное

прикладное значение раскрасок графов для задач теории расписаний, задач экономии памяти, задач распределения ресурсов и многих других задач (см. [3-12]).
Для нас важно отметить, что попытки решить проблему четырех красок привели Биркгофа [13] к понятию хроматического многочлена карты. В работе Уитни [14] это понятие было расширено до понятия хроматического многочлена произвольного графа и получен ряд фундаментальных свойств хроматических многочленов графов. Необходимо также отметить работу Биркгофа и Лыоиса [15], в которой были получены некоторые результаты о хроматических многочленах планарных графов и сформулированы нерешенные задачи. Большое значение для исследования хроматических многочленов графов имела обзорная статья Рида [16], в которой были подведены некоторые итоги и сформулированы открытые вопросы. Детальную информацию о современном состоянии теории хроматических многочленов графов можно найти в обзорных статьях [17-21] и монографиях [22] и [23].
Перейдем теперь к точному определению используемых нами понятий и к формулировке цели исследования.
В данной работе мы рассматриваем только обыкновенные графы, т. е. графы без петель и кратных ребер. Обозначения и терминологию для графов будем использовать в соответствии с [24].
Пусть Є - произвольный (гг, ггг, /г)-граф, т. е. граф, имеющий п вершин, т ребер и к компонент связности. Раскраской, или Ь-раскраской графа С? называется отображение ф из множества вершин V в множество натуральных чисел {1,2,... Д} такое, что для любых двух различных смежных вершин и и V графа (3 выполняется ф{и) ф ф(у), т. е. любые две различ-

ке должны быть использованы все х цветов. Хорошо известно (см., например, [16] или [24]), что функция Р{С,х) является многочленом степени та от ж, который называют хроматическим многочленом графа С?.
Два графа называются хроматически эквивалентными, или х-эквивалентными-, если они имеют одинаковые хроматические многочлены.
Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвариантами являются число вершин, число ребер и число компонент связности графа (см. [16] или [24]). Число ребер графа С? будем обозначать через /2(6?)- Отметим, что число вершин графа С можно было бы обозначать через 1(С).
Укажем еще два хроматических инварианта для графов (см. [25] или [26]):
13(С)=Д(С)
— число треугольников в графе Є]
14(0) = идП (О)-2М (С),
где через ид Щ (С) мы обозначаем число вершинно порожденных подграфов вида Д в графе Є, т. е. число бесхордных 4-циклов в О, а через Д (С) — число полных четырехвершии-ных подграфов КА в графе С?.
Через рДС, г) будем обозначать число разбиений множества вершин графа б наг непустых коклик, т. е. подмножеств, со-