Связи различных хроматических характеристик графов

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

Глава I. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ

§ I. Основные оцределения теории графов

§ 2. Раскраска графов. Хроматический многочлен графов

Глава II. ОДНОЗНАЧНО И ЛОКАЛЬНО ОДНОЗНАЧНО РАСКРАШИВАЕМЫЕ ГРАФЫ

§ I. Однозначно раскрашиваемые графы с наименьшим числом

ребер

§ 2. Класс к-деревьев

§ 3. Элементарные двудольные мультиграфы

§ 4. Локально однозначно раскрашиваемые графы

Глава III. ХРОМАТИЧЕСКИЙ МНОГОЧЛЕН ГРАФОВ

§ I. Хроматически эквивалентные и биэквивалентные графы • § 2. Сильно и слабо циклические графы с целочисленными
хроматическими спектрами
§ 3. Хроматически единственные графы и классы графов «
ЛИТЕРАТУРА

В настоящее время графы и связанные с ними методы исследований органически цронизывают на разных уровнях едва ли не всю современную математику. Теория графов эффективно используется в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Теория графов находит широкое применение в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. В то же самое время теория графов вместе со смежным с ней комбинаторным анализом постепенно превращается из набора искусственных приемов решения отдельных задач в стройный и цельный раздел современной математики.
Одним из центральных разделов теории графов являются задачи раскраски графов, возникшие в связи со знаменитой проблемой четырех красок (решенной спустя 100 лет Аппелем и Хакеном [9, 10]).
Сама по себе проблема четырех красок едва ли имеет какие-либо важные приложения. Однако эта цроблема сыграла большую роль в развитии всей теории графов. Попытки ее решения привели, в частности, к продвижению двух следующих направлений: чисто комбинаторной характеризации планарных графов и изучения хроматических свойств графов общего вида, каждое из которых, как известно, имеет непосредственное применение и в чистой математике, и в практике.
Насколько трудна задача раскраски графов, показывает принадлежность к классу Д/Р -полных задач даже таких частных задач, как раскрашиваемость графа в 3 цвета [4] или рас-

краска планарных однородных степени 4 графов 8].
Вряд ли стоит здесь пытаться рассмотреть все направления исследований в раскраске графов. Шесто этого лишь укажем направления, к которым принадлежат результаты предлагаемой диссертации: изучение структур однозначно раскрашиваемых или близких к ним по свойствам графов, установление связей между хроматическим многочленом и некоторыми характеристиками графов.
Диссертация состоит из введения и трех глав. Для удобства читателя нумерация теорем и т.д. трехиндексная, новые результаты начинаются с цифры, означающей номер главы, далее идут номер параграфа и порядковый номер соответствующего утверждения, ранее известные результаты начинаются с первых трех букв А, Бг и В русского алфавита, соответственно относящих .эти результаты к одной из трех глав.
Переходим к обзору основных результатов диссертации.
Глава I содержит основные определения и обозначения. Вторая Глава IIосвящена однозначно к-раскрашиваемым графам, о которых цри к^З известно мало. Более того, доказано, что задача распознавания однозначной к -раскрашиваемости к-раскрашенного графа при принадлежит классу Л/Рполных проблем [в]. Основной результат § I связан с гипотезой: каждый однозначно 4-раскрашиваемый планарный граф тлеет минимальную степень, равную 3. Здесь рассматривается класс однозначно к-раскрашиваемых графов с наименьшим числом ребер. В частности, класс
г|Ц
содержит все однозначно 4-расщ)ашиваемые планарные графы. В теореме 2.1.1 доказано, что для любых кг-2. и к-'! ^ <В^2к-3 в классе существует граф (л с минимальной степенью .Из

И пусть 'гХ/^и и/^1 - разбиение на одноцветные
классы множества вершин в Ц-раскраске ар', с= 1,2. . Мультиграф раскрасок строится следующим образом.
Вершинами 1-ой доли М служат классы ^ /ц > й-4)2
Для каждой вершины х <$■ /(&) находятся классы V* и '/^ , содержащие ее (по определению раскраски они существуют и единственные) и в М вершины V* и /£ соединяются ребром. В дальнейшем вершину графа (•* , ей соответствующее ребро мультиграфа М и вершину реберного графа Ь(М) , соответствующую этому ребру будем обозначать одним и тем же символом, т.е. будем считать, что !/(&)“ ЕСМ") г ^/( . Поэтому,
нацример, равенство будет означать, что они как
помеченные графы идентичны.
ЛЕММА 2.3,1. Пусть - произвольный помеченный граф с некоторыми Ц-раскрасками "ць с = 1,2» . Тогда граф & является еуграфом дополнения реберного графа мультиграфа раскрасок М= /М&р,0'уг.') .Причем 6|=Т]4ч) тогда и только тогда, когда & См^Уг) -максимален.
Доказательство. Пусть (3* Сфи'Ч5*.') -максимален. Тогда две вершины X и у графа смежны тогда и только
тогда, когда Хр^Ск) 4 "Ц» ■С/) С =^2. » т.е. когда и в первом, и во втором разбиениях принадлежат разным классам. Следовательно, ребра х и у в не инцидентны, т.е. в графе СОЛ вершины X И у смежны.
Обратно, пусть (о & 1_|(К). Тогда две вершины >< и у
графа смежны тогда и только тогда, когда вершины X и у графа не смежны. Последнее возможно в том и только в том случае, если ребра у и у в мультиграфе М не инцадентны. Таким образом, вершины /■ и у графа (-? при-