Решетки разбиений натуральных чисел и хроматическая определяемость графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

° ' УДК 512 56 519 17

Королева Татьяна Александровна

РЕШЕТКИ РАЗБИЕНИЙ НАТУРАЛЬНЫХ ЧИСЕЛ И ХРОМАТИЧЕСКАЯ ОПРЕДЕЛЯЕМОСТЬ ГРАФОВ

01 01 06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

I

х г хеза

Екатеринбург — 2008

003171688

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им А М Горького

Научный руководитель: доктор физико-математических наук,

профессор В А Баранский

Официальные оппоненты: доктор физико-математических наук,

профессор В И Зенков

кандидат физико-математических наук, доцент Е А Перминов

Ведущая организация: Южно-Уральский государственный

университет

Защита диссертации состоится 17 июня 2008 года в 14 часов на заседании диссертационного совета Д 004 006 03 в Институте математики и механики УрО РАН по адресу

620219, г Екатеринбург, ул С. Ковалевской, 16

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН

Автореферат разослан мая 2008 г.

Ученый секретарь диссертационного совета, доктор физ -мат наук

В В Кабанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

Одна из наиболее известных задач теории графов — проблема четырех красок Более чем столетняя история попыток решения этой проблемы сыграла положительную роль в развитии различных разделов теории графов и особенно для исследования свойств раскрасок графов Во многих работах было показано важное прикладное значение раскрасок графов для задач теории расписаний, задач экономии памяти, задач распределения ресурсов и многих других задач (см. [1-5])

Для нас важно отметить, что попытки решить проблему четырех красок привели Биркгофа [6] к понятию хроматического многочлена карты В работе Уитни [7] это понятие было расширено до понятия хроматического многочлена произвольного графа и получен ряд фундаментальных свойств хроматических многочленов графов Необходимо также отметить работу Биркгофа и Льюиса [8], в которой были получены некоторые результаты о хроматических многочленах планарных графов и сформулированы нерешенные задачи Большое значение для исследования хроматических многочленов графов имела обзорная статья Рида [9], в которой были подведены некоторые итоги и сформулированы открытые вопросы Детальную информацию о современном состоянии теории хроматических многочленов графов можно найти в обзорных статьях [10-14] и монографиях [15] и [16] В данной работе мы рассматриваем только обыкновенные графы, т е графы без петель и кратных ребер Обозначения и терминологию для графов будем использовать в соответствии с [17]

Пусть б - произвольный (п,ш, &)-граф, т е граф, имеющий п вершин, т ребер и к компонент связности Раскраской, или раскраской графа б называется отображение ф из множества вершин V в множество натуральных чисел {1,2, , ¿} такое, что для любых двух различных смежных вершин и к V графа О выполняется ф(и) ф Ф(у), т е любые две различные смежные вершины имеют разный "цвет" Граф называется Ь-раскрашиваемым, если он обладает ^раскраской и — Ахроматическим, если он ¿-раскрашиваемый, но не является {£ — 1)-раскрашиваемым, в этом случае число Ь называется хроматическим числом графа б и обозначается через х((?)

Для натурального числа х через Р(/3,х) обозначим число всевозможных раскрасок графа Свг заданных цветов, причем не предполагается, что в раскраске должны быть использованы все х цветов Хорошо известно (см [9] или [17]), что функция Р(С,х) является многочленом степени п от х, который называют хроматическим многочленом графа в Два гра-

фа называются хроматически эквивалентными, или х~эквивалептнъши, если они имеют одинаковые хроматические многочлены

Граф называется хроматически определяемым, или х~определяемъш, если он изоморфен любому хроматически эквивалентному ему графу Это понятие ввели в 1976 г Chao С Y. и Е G Whitehead Jr. [21] Различными авторами были проведены многочисленные исследования по изучению хроматической эквивалентности и хроматической определяемости для графов В этих исследованиях большое место было уделено изучению хроматической определяемости полных многодольных графов

Граф G называют t-долъным графом, если множество его вершин можно разбить на t непустых подмножеств (долей) так, что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли, если каждая вершина из одной доли соединена с каждой вершиной из других долей, то G называют полным t-дольным графом и обозначают через К(п\,п2, . ,гц), где щ,п2>. ,Щ ~ последовательность чисел элементов для всех t долей этого графа

В 1990 г. Koh К М и Тео K.L [11] доказали, что полный двудольный граф К{т11,П2) хроматически определяем при щ >n¡ > 2

Следующие полные трехдольные графы хроматически определяемые (см [22-26] и [16]).

1 Граф К(п - k, п, тг) при п>к-(- у

2. Граф К(п,п,п + к) при п > Цр-

3 Граф К(п — k,n,n + k) при п>к2 + ^к

4 Граф К(п — 4, п,п) при п > 6

5 Граф К(п — к, п, п) для любых целых чисел пик таких, что п > А: + 2 > 4

6 Граф К(п — к,п — 1,п) для любых целых чисел п и к таких, что п > 2к > 4

Следующие полные многодольные графы хроматически определяемые (см [27-29] и [16])

7 Граф К(пит,... ,nj), если |п, - п}\ < 1 для всех г,,? = 1,2,

8. Граф К(п — 1, п,. , тг, тг 4-1) при t > 2 и п > 3

9 Граф К(1,П2, .,тц) тогдаи только тогда, когдатах{щ,п2,.. ,щ}<2

10 Граф К(п — к,п,п,... , п) для любых положительных целых чисел п>к + 2, к>2

И Граф К(п — к, п~ 1,п, , п) для любых положительных целых чисел п>2к,к>2

12 Граф К(п1,п2, , тц), если |я, —п3\ = 2 и тгп{щ,П2,. ,гц}>Ь +1

Основной открытый вопрос в данной области состоит в следующем является ли хроматически определяемым полный многодольный граф . ,71*) при Ь > 3 и Щ > 77,2 > • > Щ > 2?

Цель работы — предложить некоторый новый и систематический подход к изучению хроматической определяемости полных многодольных графов, использующий вводимый нами решеточный порядок на множестве таких графов и использующий хроматические инварианты графов, найти новые естественные классы хроматически определяемых полных многодольных графов

Основные методы исследования

Доказательство хроматической определяемости полных многодольных графов проводится с помощью свойств хроматических инвариантов и взаимосвязи этих свойств с решеточными порядками на множествах полных многодольных графов

Научная новизна работы

Основные достижения диссертации заключаются в следующем

1 Доказано, что множество ЫРЬ{п) всех разбиений натурального числа п является решеткой относительно отношения >, описание которого приводится ниже

2 Доказано, что множество iV.PL всех разбиений всех натуральных чисел является решеткой относительно отношения >, описание которого приводится ниже

3. Предложен новый подход к изучению хроматической определяемости полных многодольных графов, основанный на использовании решеточного порядка

4 Доказана хроматическая определяемость атомов в решетках полных многодольных графов NРЬ(п, £)

5 Доказана хроматическая определяемость полных трехдольных п-гра-фов с неодноэлементными долями, имеющих высоту Л < 3 в решетках

ИРЦп, 3)

Практическая и теоретическая ценность

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

Апробация результатов

Изложенные в диссертации результаты были представлены на заседании Уральского математического общества (Екатеринбург, 2007), на XXXIX-ой региональной молодежной конференции (Екатеринбург, 2008), на XV Международной конференции студентов, аспирантов и молодых ученых "Ломоносов — 2008" (Москва, 2008), на семинаре отдела алгебры и топологии Института математики и механики УрО РАН (Екатеринбург, 2008) По результатам работы автор неоднократно выступал на семинаре "Алгебраические системы" (Екатеринбург, 2007-2008)

Публикации

Основные результаты диссертации опубликованы в пяти работах, список которых приведен в конце автореферата [32-36] Результаты работ [32] и [34] получены автором и В А Баранским в нераздельном соавторстве

Структура диссертации

Текст диссертации состоит из введения, трех глав, списка литературы, включаещего 40 наименований Общий объем диссертации составляет 133 страницы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении описана предыстория и актуальность темы диссертации, определены цели работы, введены основные понятия, кратко изложено содержание диссертации

Первая глава посвящена описанию некоторой новой решетки разбиений натуральных чисел В первом параграфе рассмотрено понятие разбиения натурального числа и введены понятие элементарного преобразования разбиения и отношение > частичного порядка на множестве ЛгРЬ(п) всех разбиений натурального числа п

Понятие разбиения натурального числа впервые появилось в 1669 году в письме Лейбница к Иоганну Бернулли Основы же теории разбиений

чисел были заложены Эйлером В монографии [31] можно ознакомиться с историей этой теории и многочисленными ее достижениями

Разбиением натурального числа п называется невозрастающая последовательность целых неотрицательных чисел

и={щ,и2,...)

такая, что щ > > , причем и содержит лишь конечное число ненулевых компонент и п ~ и, Число I такое, что I > 1, щ > 0 и щ+1 = щ+2 = . . = 0 назовем длиной разбиения и и обозначим через 1(и) Мы будем писать п = пит(и).

Разбиение натурального числа удобно изображать в виде так называемой диаграммы Ферре, которую можно представлять себе в виде вертикальной стенки, сложенной из кубических блоков одинакового размера Вот пример такой диаграммы

На указанной диаграмме представлено разбиение 19 = 6+4+4+2+1+1+1 числа 19 на 7 слагаемых Здесь 7 — длина разбиения (6,4,4,2,1,1,1) Через ИРЬ, КРЬ(п), МРЬ(п, £) обозначим соответственно

— множество всех разбиений всех натуральных чисел,

— множество всех разбиений натурального числа п,

— множество всех разбиений длины t натурального числа п

Введем понятие элементарного преобразования разбиения и = (щ, и2, . , щ) числа п = пит(и) Предположим, что существуют натуральные числа г,2 € {1,2, . г < ] такие, что

1) и, — 1 > и Щ-1 > и3 + 1,

2) и, = и, + 6, где 5 > 2

Будем говорить, что разбиение V — (иьи2, 1, по-

лучено элементарным преобразованием (или перекидыванием блока) разбиения и — (и\,и2,. .,и„ .,щ) Отметим, что V отличается от и точно на двух компонентах с номерами г и ] Для диаграммы Ферре такое преобразование означает перемещение верхнего блока г-го столбца вправо в ^-ый столбец Условия 1) и 2) гарантируют, что после такого перемещения снова получится диаграмма Ферре

Введем отношение > на множестве ЫРЦп), полагая и > V для б МРЬ(п), если V можно получить из и с помощью последовательного вы-

полнения конечного числа (возможно нулевого) элементарных преобразований

Нетрудно проверить, что отношение > на множестве ИРЬ{п) является отношением частичного порядка

Во втором параграфе на множестве МРЬ(п) вводится отношение > Полагаем в случае, если

Щ > VI Щ+Щ > VI + VI

Щ + 012 + • + К, > 1)1 + Ь2 +.. + V,

Щ+и2+ . +Щ-1 > Vl+V2 + . +^-1,

где и = (щ, иг, ■ V = («1,^2) • I ъ), £ — максимальная из длин и иу Доказано, что отношения > и> совпадают на ИРЬ{п)

Пусть даны два разбиения и = {щ,П2, .,щ),у = (г>1,г>2, .., € ЫРЬ{п), где £ — наибольшая из длин и иг; Укажем алгоритм вычисления вспомогательной последовательности V) = ю(и, V) = (ю^тг, .)

Алгоритм 1. Полагаем Ао(и) = 0 и До(^) = 0 (это начальные запасы для и и у)

Для г = 1,2, . выполняем следующие действия до тех пор, пока не получим число го,, равное О г) полагаем

■ш, = тгп{и, + Д,_1 (и), и, + Д.-х^)} и определяем запасы для и и V после г-го этапа

Д ,(и) = + Д,-1 (и) - ъи,=и1 +и2+ +и%—из\—'Ш2 — . . — V), > 0,

Д,(и) = и, + Д,_1(«) - и;, = VI + VI + .+У1 — и}1 — ъи2 — ...—гих>() #

Установлено, что разбиение го = и>(и,у) является пересечением разбиений и и V в частично упорядоченном множестве ИРЬ(п), <

Для каждой диаграммы Ферре (разбиения) и е ЯРЬ{п) имеется коди-аграмма (коразбиение) т(и) е МРЬ(п) Рассмотрим Пример.

У

Здесь п = 26 = 6 + 5 + 3 + 3 + 2 + 2 + 2 + 1 + 1 + 1и/ = 10 Поменяем ролями оси х и у, т е рассмотрим новую диаграмму, роль столбцов которой играют строки исходной диаграммы Тогда мы получим кодиаграмму исходной диаграммы, для которой п = 26 = 10+7+4+2+2+1 В общем случае кодиаграмма т(и) строится по диаграмме и аналогичным образом

Отображение т является инволютивным антиавтоморфизмом частично упорядоченного множества NPL(n), < Отсюда вытекает, что для любых ц, v G NPL(n) выполняется

и V v — т(т(и) A r(v))

— объединение разбиений и и v в частично упорядоченном множестве NPL(n),<

Отметим, что последнее равенство дает нам естественный алгоритм вычисления объединения и Vv, в котором используется переход к кодиаграм-мам и алгоритм вычисления пересечения т(и) A t(v) Первый основной результат главы 1 — следующая

Теорема 1. Множество NPL(n) является решеткой относительно отношения >

Эту решетку мы будем называть решеткой разбиений натурального числап. Устройство решетки NPL(9) продемонстрировано на Рис. 1, здесь через ту. к, где т,к — натуральные числа, мы обозначаем последовательность, составленную из к экземпляров числа m

•от \(8,1)

(в, 3b/ \(7,1,1) (5,4) /

(4,4,\(5.2,2)\(6,1хЗ) 3,1,0ч

(3,3,3)< >(5,1x4)

\ 1Ч4,2,2,П/

(3,3,2,т<^ \|4,2,1хЗ)

(3,2x3)«^ \(3,3,1x3^(4,1x5)

(3,2,2,1,т<^ у/

(2x4,1)«^ N<«,2,1x4)

(2x3,1x3^ \(3,1хв)

^»(2,1x7)

Wwi) Рис 1 ЛГР£(9)

В третьем параграфе рассмотрено множество NPL всех разбиений всех натуральных чисел Ясно, что множество NPL равно дизъюнктному объединению множеств NPL(n), где п = 1,2,.. .

В число элементарных преобразований разбиений из NPL включим все элементарные преобразования разбиений из множеств вида NPL(n) и добавим новые, которые будем называть удалениями блоков.

Пусть и = (ui,U2, . ) G NPL и и% — 1 > «t+j Преобразование, которое заменяет и на и' = (щ,и2, .,u,-i,u, — 1,и,+ь и,+г, ■■) будем называть удалением блока

На множестве NPL определим отношение р, полагая upv, если v можно получить из« с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований всех рассмотренных типов Отношение р является отношением частичного порядка и для любого натурального п на множестве NPL(n) С NPL отношение р совпадает с ранее рассмотренным отношением >, так как из rmm(u) = num(v) и upv следует и > v В силу этого отношение р далее будем обозначать через >.

Отношения определенные нами на всех NPL(n), продолжим на NPL,

полагая и — (щ, щ, . ) Р* V — (г^,г^,...)) если

«1 + И2 + - • + > VI + щ + .. (г = 1,2,. .).

Далее установлено, что отношения > и & совпадают на ЫРЬ Второй основной результат главы 1 — следующая

Теорема 2. Множество МРЬ является решеткой относительно отношения >

Эту решетку мы будем называть решеткой разбиений натуральных чисел Устройство нижней части решетки ЫРЬ продемонстрировано на Рис 2 Заметим, что алгоритм 1 вычисляет пересечение двух произвольных разбиений из ИРЬ, а в доказательстве теоремы 2 мы фактически указываем алгоритм вычисления объединения двух разбиений из ИРЬ

На множестве ИРЬ хорошо известны два других решеточных порядка — порядок Юнга, дающий решетку Юнга [30], и лексикографический порядок.

Пусть и = («1, «2,...), V = (VI, г>2, • ) — два разбиения из NРЬ Порядок Юнга и>:ь определяется условием

Щ > VI,«г > «2,. .

Очевидно, ЫРЬ, < является решеткой, которую называют решеткой Юнга Из определения порядка Юнга следует «I.+их>У1+Ь2+...+ь,

(г — 1,2,. .), т е введенный нами порядок > на ИРЬ продолжает порядок Юнга

Нетрудно заметить, что наш порядок на ЫРЬ продолжается до лексикографического порядка.

Далее мы применим решетки ИРЬ(п) для изучения хроматических многочленов графов. Собственно, изучение свойств хроматических многочленов графов и привело нас к идее рассмотрения указанных решеток

Рис 2

Во второй главе предложен новый подход к изучению хроматической определяемое™ полных многодольных графов, основанный на использовании решеточного порядка, рассмотренного в главе 1 Четвертый параграф посвящен основным определениям и обозначениям, проведено описание хроматических инвариантов графов и их свойств

Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов Хроматическими инвариантами являются число вершин, число ребер и число компонент

связности графа (см. [9] или [17]). Число ребер графа С? будем обозначать через /г(<3) Отметим, что число вершин графа С? можно было бы обозначать через 11(0) Укажем еще два хроматических инварианта для графов (см [18] или [19])

/3(С?)=Д(С7)

— число треугольников в графе <3,

14(С) = У9ЩО)-2ЩО),

где через удЩ(0) мы обозначаем число вершинно порожденных подграфов вида П в графе (?, те число бесхордных 4-циклов в С, а через И (С?) — число полных четырехвершинных подграфов в графе Д.

Через р£(С,г) будем обозначать число разбиений множества вершин графа (7 на г непустых коклик, т. е подмножеств, состоящих из попарно несмежных вершин графа С. По теореме Зыкова (1952) (см [20])

п

где через х^ обозначается факториалъная степень переменной х, т. е яМ _ х(х—1)(х — 2) . (х — г +1), а через х — хроматическое число графа <3 (наименьшее число красок, необходимое для раскраски графа б) В силу указанной теоремы числаг) при X < г < га являются хроматическими инвариантами

Пусть п = П1 + П2 + . где щ > щ > > щ > 1, — разбиение

числа п Через К(п1,п2,.. будем обозначать полный ¿-дольный граф на п вершинах с долями размеров п\,П2, .,гц. Ясно, что с точностью до изоморфизма существует взаимно однозначное соответствие между полными ¿-дольными графами на п вершинах и элементами решетки МРЬ(п,1) Поэтому порядок < на ИРЬ(п, ¿) индуцирует отвечающий ему порядок на множестве таких графов. Мы можем отождествлять полный многодольный п-граф с соответствующим разбиением числа п

Зафиксируем элементарное преобразование разбиений из ИРЬ(п, £)

и-(иьи2,.. .,и„. =>ь = (щ,и2, и, — 1, 4-1,..

где г < з, иг = и} + 6 и 6 > 2

Для графа К(щ,щ,хроматический инвариант /г кратко будем записывать в виде /г(«). Аналогично мы будем поступать и для других хроматических инвариантов Инварианты 12 и обладают следующими свойствами

Ми) ~ h(v) = -(Ö - 1 )(п - и, - щ)

Пусть задан полный i-дольный граф К(щ,П2, ,тц), где щ > п2 > > тц > 1, и граф Я получен из него удалением непустого семейства ребер Е, т е Н — К(щ,П2,- ,nt) — Е

Можно показать, что инварианты h при переходе от К(щ, п2, , гц) к Я изменяется следующим образом /з(Я) = I3{K{nhn2, ,гн)) - 6 + 6 + 2£з, т е

- - 2Сз = -(/з(«> - /з(«)), (1)

где 6 = 12eeE&(e)> а б(е) — число треугольников в К(щ, п2, ,тц), содержащих заданное ребро е £ Е,

— число треугольников в K{ni,n2, ■ содержащих два смежных

ребра из Е и содержащих одно ребро, не принадлежащее Е, £з — число треугольников в Е

Для выяснения поведения инварианта /4 используется следующее равенство

1А(Н)-и(К(пип2,.. ,nt))=^n(Я)-г^Цп2, ))-

2(Ш(Н)-ЩК(щ,п2,

При t = 3 рассмотриваются три случая /) г = 1, j = 2, \) г = 2, j = 3 и 1) г = 1, з = 3 В этих случаях инварианты /3 и /4 обладают свойствами /)h(u)-h(v) = -(6-l)n3, \) h(u) — h(v) = —(S — l)ni, i)h{u)-h(v) = -(5-l)n2,

/) h(u) - h(v) = -(6 - 1) [feb&ä - (*)] ,

\) h(u) - h(v) = -(<5 - 1) _ (m) >

!) h(u) - h(v) = -(6 - 1) [M- _ (n3) _

Заметим, что при t — 3 граф К(п1,п2,пз) не содержит подграфов Kj и поэтому I4(u) = vg П (К(пи п2, Пз)).

Можно показать, что инвариант /4 при переходе от К{п\, п2,пз) к Я изменяется следующим образом

h(H) = h(ni,n2, Пз) + - т/1 + гц + 2щ + Зщ, т е

i?-ih+Tfc + 2»fe + 3in = h(u)-I4(v), (2)

где г) — число подграфов вида г><? П (бесхордный цикл длины четыре), возникающих при удалении Е из К(щ,п2,щ),

1)1 = J^eeE1)Áe)> a VÁe) — число бесхордных 4-циклов в К(щ, П2,Пз), содержащих заданное ребро е Е Е,

t¡2 — число бесхордных 4-циклов в К(п\,п2,п%), содержащих точно два ребра из Е,

г/з — число бесхордных 4-циклов в К(п\,п2, пз), содержащих точно три ребра из Е,

7/4 — число бесхордных 4-циклов в К(п1,п2,пз), содержащих точно четыре ребра из Е.

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

В 1982 г Chao С Y и G A Novacky Jr [27] доказали, что хроматически определяются полные í-дольные n-графы вида K(q + 1, ,9 + 1, 9,. ,q), где компонента q+1 повторяется г раз, а компонента q повторяется s — t—r раз Здесь q — частное, а г — остаток при делении п на t Иными словами, хроматически определяются полные многодольные графы, являющиеся наименьшими элементами в решетках NPL(n,t)

Легко видеть, в решетке NPL(n, t) имеется не более двух атомов, т е разбиений, покрывающих наименьшее разбиение и — (<7 + 1, ,9 + 1, q, , q) Эти атомы имеют вид

«i = (í + l, >9 + 1,Я, ..,9,9-1), (3)

где компонента 9 + 1 повторяется г +1 раз, компонента q повторяется s — 2 раза, и

«2 = (9 + 2,9 + 1, ,9 + 1,9,. .,9), (4)

где компонента 9 + 1 повторяется г — 2 раза, а компонента q повторяется s + 1 раз

Основной результат главы 2 — следующая

Теорема 3. Пусть (ni,n2, • ,nt) — разбиение, являющееся атомом решетки разбиений натурального числа п Hat слагаемых, щ > .. > гц > 2 и 3 < í Тогда полный многодольный граф К(п\,п,2, , п() хроматически определяем

Отметим, что частный случай теоремы при г = 0 был получен в 1988 г. Giudici R Е и Lopez М А. [28] Другой частный случай следует из результата Zhao Н X [16], но при условии q>t + 2

В третьей главе доказала хроматическая определяемость полных трехдольных n-графов, находящихся на нижних "этажах" решеток NPL(n, 3) Для доказательства используется метод описанный во второй главе и свойства хроматических инварантов Глава разделена на три параграфа в соответствии со значением остатка при делении п на 3 Основной результат главы — следующая

Теорема 4. Пусть п — натуральное число и h — неотрицательное целое число < 3 Тогда любой полный трехдольный п-граф с неодноэлементными долями, имеющий высоту h в решетке NPL(n,3), является хроматически определяемым

Отметим, что данная теорема обобщает и усиливает ряд ранее полученных результатов других авторов

Благодарности

Автор выражает глобокую признательность своему научному руководителю профессору Виталию Анатольевичу Баранскому за постановку задачи, постоянное внимание к работе и всесторонную поддержку Автор благодарит весь коллектив кафедры алгебры и дискретной математики за создание творческой обстановки

Список литературы

[1] Евстигнеев, В.А. Применение теории графов в программировании /Под ред А П Ершова — M Наука, 1985

[2] Кристофидес, Н. Теория графов Алгоритмический подход — M Мир, 1978

[3] Рейнгольд, Э., Нивергельт, Ю., Део, Н. Комбинаторные алгоритмы Теория и практика — M Мир, 1980

[4] Свами, М., Тхуласираман, К. Графы, сети и алгоритмы — M Мир, 1984

[5] Харари, Ф. Теория графов — M Мир, 1973

[6] Birkhoft, G.D. A determinant formula for the number of ways of coloring a map//Annal Math 2nd Ser , 1912-1913 Vol 14 P. 42-46

[7] Whitney, H. The coloring of graphs // Annal Math , 1932 Vol 33 P. 688-718

[8] Birkhoft, G.D., Lewis, D. Chromatic polynomials // Trans Amer Math Soc, 1946 Vol 60 P 355-451

[9] Read, R.C. An introduction to chromatic polynomials //J Comb Theory, 1968 Vol 4 P 52-71

[10] Read, R.C., Tutte, W.T. Chromatic polynomials — In Selected Topics in Graph Theory III Academic Press 1988

[11] Koh, K.M., Teo, K.L. The search for chromatically unique graphs // Graphs Combin ,1990 Vol 6 P. 259-285

[12] Koh, K.M., Teo, K.L. The search for chromatically unique graphs II // Discrete Math 1997 Vol 172 P 59-78

[13] Chia, G.L. Some problems on chromatic polynomials // Discrete Math 1997 Vol 172 P 39-44

[14] Liu, R.Y. Adjoint polynomials and chromatically unique graphs // Discrete Math 1997 Vol 172 P 85-92

[15] Dong, P.M., Koh, K.M., Teo, K.L. Chromatic polynomials and chromaticity of graphs — Monograph, Preprint, 2004

[16] Zhao, H. Chromaticity and adjoint polynomials of graphs — Wohrmann Print Service, The Netherlands, 2005

[17] Асанов, M.O., Баранский, B.A., Расин, B.B. Дискретная математика графы, матроиды, алгоритмы — Ижевск НИЦ "Регулярная и хаотическая динамика", 2001

[18] Farrell, E.J. On chromatic coefficients // Discrete Math. 1980 Vol 29 P 257-264

[19] Баранский, B.A., Вихарев, C.B. О хроматических инвариантах двудольных графов // Известия Уральского гос университета, 2005 Математика и механика Вып 7 №36 С 25-34

[20] Зыков, А.А. Основы теории графов — М . Наука, 1987

[21] Chao, C.Y., E.G. Whitehead, Jr. On chromatic equivalence of graphs In Theory and applications of graphs (Proc Internath. Conf, Western Mich Univ., Kalamasoo, 1976) — Lecture Notes in Math , Vol 642, P 121-131 - Springer, 1978

[22] Zou, H.W. The chromaticity of the complete tripartite graph К(n — 4; n, n) (Chinese) // J Shanghai Teachers Univ (Natur Sci) 1998 Vol 1. P 37-43

[23] Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph K(n — k,n,n) (Chinese) // J Shanghai Teachers Univ (Natural Sc) 1999 Vol 1 P 15-22

[24] Zou, H.W. The chromatic uniqueness of complete tripartite graphs K(nhn2,n3) (Chinese) // J Sys Sci. Math. Sci 2000 Vol 20 P 181186

[25] Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph K(n, n,n + k) (Chinese) // J Shanghai Teachers Univ (Natur Sci) 2000 Vol 3 P. 29-35

[26] Zou, H.W. The chromatic uniqueness of certain complete tripartite graphs K(m,n,r) 11 J. Math (Wuhan) 2003 Vol 23 P 307-314

[27] Chao, C.Y., G.A. Novacky, Jr. On maximally saturated graphs // Discrete Math 1982 Vol 41 P 139-143

[28] Giudici, R.E., Lopez, M.A. Chromatic uniqueness of sKn, Report No 85-03, Dpto de Mat у Ciencia de la Сотр. Univ Sim on Bolivar,1985

[29] Li, N.Z., Liu, R.Y. The chromaticity of the complete f-partite graph K{l,P2, )Pt) 11 J Xinjiang Univ Natur Sci 1990 Vol 7 No3 P 95-96

[30] Айгнер, M. Комбинаторная теория. — M Мир, 1982

[31] Эндрюс, Г. Теория разбиений — М Наука, 1982

Работы автора по теме диссертации

[32] Баранский, В.А., Королева, Т.А. Хроматическая определяемость атомов в решетках полных многодольных графов // Труды Института математики и механики УрО РАН 2007 Том 13, №3. С 22-29

[33] Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов I // Труды Института математики и механики УрО РАН 2007 Том 13, №3 С 65-83

[34] Баранский, В.А., Королева, Т.А. Решетка разбиений натурального числа // Доклады Академии Наук 2008 Том 418, №4 С 439-442

[35] Королева, Т.А. О хроматической определяемое™ полных трехдольных графов // Труды XXXIX Молодежной конференции ИММ УрО РАН, Екатеринбург 2008 С 23-27

[36] Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов // Сборник тезисов XV Международной конференции студентов, аспирантов и молодых ученых "Ломоносов-2008" С

47

одписано в печать Об. С61И 00<£ лоская печать

Формат 60x84 1/16 Тираж 100

Бумага писчая Заказ 203

Ризография НИЧ ГОУ ВПО УГТУ-УПИ 620002, г Екатеринбург, ул Мира 19

Введение

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

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

2 Решетки ИРЦть).

3 Решетка ИРЬ

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

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

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

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

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

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

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

Одна из наиболее известных задач теории графов — проблема четырех красок. Имеются сведения, что Мёбиус был знаком с этой проблемой в 1840 г., и достоверно известно, что Гутри сообщал де Моргану о данной проблеме в 1850 г. Первое из многих ошибочных доказательств было дано Кемпе [1] в 1879 г. Ошибку в доказательстве Кемпе в 1890 г. обнаружил Хивуд [2], который тогда же установил, что гипотеза верна, если "четыре" заменить на "пять". Иными словами, Хивуд доказал, что любой планарный граф раскрашивается в пять красок.

В 1969 г. проблема четырех красок была сведена X. Хе-ли к рассмотрению весьма большого конечного числа случаев. Наконец, в 1976 г. Аппелль и Хейкен решили проблему четырех красок, но, возможно, не самым лучшим способом. Решение потребовало длительного перебора компьютером огромного числа случаев. Сам факт компьютерного решения проблемы четырех красок является, несомненно, выдающимся достижением, которое вполне достаточно для прекращения поиска контрпримера.

Более чем столетняя история попыток решения этой проблемы сыграла положительную роль в развитии различных разделов теории графов и особенно для исследования свойств раскрасок графов. Во многих работах было показано важное прикладное значение раскрасок графов для задач теории расписаний, задач экономии памяти, задач распределения ресурсов и многих других задач (см. [3-12]).

Для нас важно отметить, что попытки решить проблему четырех красок привели Биркгофа [13] к понятию хроматического многочлена карты. В работе Уитни [14] это понятие было расширено до понятия хроматического многочлена произвольного графа и получен ряд фундаментальных свойств хроматических многочленов графов. Необходимо также отметить работу Биркгофа и Льюиса [15], в которой были получены некоторые результаты о хроматических многочленах пла-нарных графов и сформулированы нерешенные задачи. Большое значение для исследования хроматических многочленов графов имела обзорная статья Рида [16], в которой были подведены некоторые итоги и сформулированы открытые вопросы. Детальную информацию о современном состоянии теории хроматических многочленов графов можно найти в обзорных статьях [17-21] и монографиях [22] и [23].

Перейдем теперь к точному определению используемых нами понятий и к формулировке цели исследования.

В данной работе мы рассматриваем только обыкновенные графы, т. е. графы без петель и кратных ребер. Обозначения и терминологию для графов будем использовать в соответствии с [24].

Пусть С - произвольный (гг, гтг, к)-граф, т. е. граф, имеющий п вершин, т ребер и к компонент связности. Раскраской, или ¿-раскраской графа С называется отображение ф из множества вершин V в множество натуральных чисел {1, 2,., £} такое, что для любых двух различных смежных вершин и и V графа С? выполняется ф{и) ф Ф{у), т. е. любые две различные смежные вершины имеют разный "цвет". Граф называется раскрашиваемым, если он обладает ¿-раскраской и — Ахроматическим, если он ¿-раскрашиваемый, но не является (£ — 1)-раскрашиваемым; в этом случае число £ называется хроматическим числом графа С* и обозначается через

Для натурального числа х через Р(С, х) обозначим число всевозможных раскрасок графа (3 в х заданных цветов, причем не предполагается, что в раскраске должны быть использованы все х цветов. Хорошо известно (см. [16] или [24]), что функция .Р(бг, х) является многочленом степени п от х, который называют хроматическим многочленом графа (?. Два графа называются хроматически эквивалентными, или х~эк~ вивалентнымщ если они имеют одинаковые хроматические многочлены.

Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвариантами являются число вершин, число ребер и число компонент связности графа (см. [16] или [24]). Число ребер графа (3 будем обозначать через /2(С). Отметим, что число вершин графа (2 можно было бы обозначать через 1\{0).

Укажем еще два хроматических инварианта для графов (см. [25] или [26]):

1г(С)=А(0) — число треугольников в графе

14(0) = идП (С)-2Ы (С), где через vg П (G) мы обозначаем число вершинно порожденных подграфов вида Щ в графе G, т. е. число бесхордных 4-циклов в G, а через М (G) — число полных четырехвершин-ных подграфов в графе G.

Через pt(G, г) будем обозначать число разбиений множества вершин графа G на г непустых коклик, т. е. подмножеств, состоящих из попарно несмежных вершин графа G. По теореме Зыкова (1952) (см. [27] или [28]) п г=Х где через х^ обозначается факториалъная степень переменной х, т. е. х^ — х(х — 1)(ж — 2). (х — i + 1), а через % —хроматическое число графа G. В силу указанной теоремы числа pt(G,i) при х < & < п являются хроматическими инвариантами.

Граф называется хроматически определяемым, или х~опРе~ деляемым, если он изоморфен любому хроматически эквивалентному ему графу. Это понятие ввели в 1976 г. Chao С.Y. и E.G. Whitehead Jr. [29]. Различными авторами были проведены многочисленные исследования по изучению хроматической эквивалентности и хроматической определяемости для графов. В этих исследованиях большое место было уделено изучению хроматической определяемости полных многодольных графов.

Граф G называют двудольным графом, если множество его вершин можно разбить на два непустых подмножества (доли) так, что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина из одной доли соединена с каждой вершиной из другой доли, то G называют полным двудольным графом.

Граф G называют t-дольным графом, если множество его вершин можно разбить на t непустых подмножеств (долей) так, что-любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина из одной доли соединена с каждой вершиной из других долей, то G называют полным t-долъным графом и обозначают через К(щ,п2,.,щ), где ni, П2,., nf — последовательность чисел элементов для всех t долей этого графа.

В 1990 г. Koh K.M. и Тео K.L. [18] доказали, что полный двудольный граф К(п1,п2) хроматически определяем при п\ > 77-2 > 2.

Следующие полные трехдольные графы хроматически определяемые (см. [30-34] и [23]).

1. Граф К(п — к, п, п) при п > к + у.

2. Граф К(п, n, п + к) при п >

3. Граф К(п - k, n, п + к) при п > к2 + ^к.

4. Граф К(п — 4, п, п) при п > 6.

5. Граф К{п — /г, п, тг) для любых целых чисел п и к таких, что п > к + 2 > 4.

6. Граф К(п — k, п — 1,тг) для любых целых чисел пик таких, что п > 2к > 4.

Следующие полные многодольные графы хроматически определяемые (см. [35-37] и [23]).

7. Граф К(п1,П2,. ■ ,nt), если \щ — щ\ < 1 для всех i:j = 1,2

8. Граф К(п — 1, п,., га, га + 1) при t > 2 и п > 3.

9. Граф К( 1, П2,.,щ) тогда и только тогда, когда max{ni, п-2, ■ • ■ ,nt} < 2.

10. Граф К(п — к, га, га,., га) для любых положительных целых чисел га > к 4- 2, к > 2.

11. Граф К(п — к, га — 1, га,., га) для любых положительных целых чисел га > 2к, к > 2.

12. Граф K(ni, щ,. ), если |raj —га^| = 2 и mm{ni, пг,. , nj >i + l.

Основной вопрос состоит в следующем: является ли хроматически определяемым полный многодольный граф К(п 1, га2,., nt) при i > 3 и ni > n<i > . > тгг > 2?

Цель данной работы:

1) предложить некоторый новый и систематический подход к изучению хроматической определяемости полных многодольных графов, использующий вводимый нами решеточный порядок на множестве таких графов и использующий указанные ранее инварианты;

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

Перейдем теперь к изложению основных результатов диссертации. Текст диссертации, следующий за введением, разделен на три главы. Основные результаты работы названы теоремами, их четыре и они имеют сквозную нумерацию.

Первая глава посвящена описанию некоторой новой решетки разбиений натуральных чисел. Понятие разбиения натурального числа впервые появилось в 1669 году в письме Лейбница к Иоганну Бернулли. Основы же теории разбиений чисел были заложены Эйлером. В монографии [39] можно ознакомиться с историей этой теории и многочисленными ее достижениями.

Разбиением натурального числа п называется невозраста-ющая последовательность целых неотрицательных чисел и = {щ,и2,.) такая, что щ > щ > . причем и содержит лишь конечное число ненулевых компонент и п — Щ. Число I такое, что I > 1, щ > 0 и щ+1 = щ+2 — . = 0 назовем длиной разбиения и и обозначим через 1{и). Мы будем писать п = пит(и) и для удобства записывать разбиение и в одном из следующих видов и = (щ, и2,.) = (щ,., щ) = (щ,. , щ, щ+х) = (щ,., ии щ+иим) = .

Разбиение натурального числа удобно изображать в виде так называемой диаграммы Ферре, которую можно представлять себе в виде вертикальной стенки, сложенной из кубических блоков одинакового размера. Вот пример такой диаграммы.

На указанной диаграмме представлено разбиение 19 = 6 + 4 + 4 + 2 + 1 + 1 + 1 числа 19 на 7 слагаемых. Здесь 7 — длина разбиения (6,4, 4, 2,1,1,1).

Потенциалом блока назовем число блоков, расположенных под данным блоком в соответствующем столбце диаграммы.

Потенциалом диаграммы назовем сумму потенциалов всех ее блоков. Потенциал диаграммы, изображающей разбиение и, обозначим через J(u).

Через NPL, NPL(n), NPL(n,t), NPL(n,s.t), где 1 < s < t <п, обозначим соответственно множество всех разбиений всех натуральных чисел; множество всех разбиений натурального числа п; множество всех разбиений длины t натурального числа п; множество всех разбиений длины I натурального числа п, для которых s < I < t.

Введем понятие элементарного преобразования разбиения u — (iii,ii2, . ,щ) числа п = num(u). Предположим, что существуют натуральные числа i,j Е {1, 2, .,£}, г < j такие, что

1) Ui — 1 > щ+1 и Uj-1 > Uj + 1;

2) щ — щ + где 6 > 2.

Будем говорить, что разбиение v = (щ, ., щ—1,., Uj+1, ., щ) получено элементарным преобразованием (или перекидыванием блока) разбиения и = (щ, W2,. . ,uj,. ,ut). Отметим, что v отличается от и точно на двух компонентах с номерами г и j. Для диаграммы Ферре такое преобразование означает перемещение верхнего блока г-го столбца вправо в j-ый столбец. Условия 1) и 2) гарантируют, что после такого перемещения снова получится диаграмма Ферре.

Введем отношение > на множестве NPL(n), полагая и > v для и, v G NPL(n), если v можно получить из и с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований.

Заметим, что после применения элементарного преобразования потенциал диаграммы уменьшается на ô — 1, так как на

6 — 1 уменьшается число блоков, находящихся под перемещаемым блоком. Следовательно, если и, V £ Л^РЬ{п) и и > V, то Ли) > Л1»)

Теперь ясно, что отношение > на множестве ЫРЬ{п) является отношением частичного порядка.

На множестве ЫРЬ(п) зададим еще одно отношение !>, полагая и Е> у в случае, если

Щ > У\ Щ + и2 > г?1 + и2 г¿l + г¿2 + . + щ > VI + у2 + . + VI

Щ + г¿2 + . + Щ-1 > VI + г>2 + . + г>г1, где и = (щ,и2,., щ), V = (^1,^2, -. •, г>г), t — максимальная из длин и и V. Конечно, здесь выполняется щ + и2 + . + щ — п = VI + У2 + .+ Vt к щ + и2 + .+ Щ = VI + У2 + .+ у3 при в > Поэтому условие, задающее отношение О, эквивалентно условию ^1+^2+ • ■ • +щ > г71+г>2+ . -Нг^ (г=1, 2,3,.). Теперь рефлексивность, антисимметричность и транзитивность отношения > очевидны, т. е. является отношением частичного порядка на МРЬ{п).

Во втором параграфе главы 1 доказано, что отношения > и ^ совпадают на ЛгРЬ(п).

Первый основной результат главы 1 — следующая

Теорема 1. Множество NРЬ(п) является решеткой относительно отношения >.

Эту решетку мы будем называть решеткой разбиений натурального числа п. Во втором параграфе указаны быстрые алгоритмы нахождения пересечения и объединения в решетке NPL(n).

Устройство решетки NPL{9) продемонстрировано на Рис. 1, здесь через m х к, где т,к — натуральные числа, мы обозначаем последовательность, составленную из к экземпляров числа т.

Ч(9)

3,3, ЗК М5,1х4)

3, 2,1x4) (3,1x6) ф, 2,1x5) ' (2,1x7)

1x9) рис. 1 NPL{ 9)

Рассмотрим теперь множество NPL всех разбиений всех натуральных чисел. Легко видеть, что множество NPL равно дизъюнктному объединению множеств NPL(n), где п — 1,2,.

В число элементарных преобразований разбиений из АТРЬ включим все элементарные преобразования разбиений из множеств вида АТРЬ(п) и добавим новые, которые будем называть удалениями блоков.

Пусть и = (и1,и2,.) е ИРЬ и щ — 1 > щ+1. Преобразование, которое заменяет и на и' = (и\, щ,., 1, щ — 1, щ+1, щ+2, • •.) будем называть удалением блока.

На множестве АТРЬ определим отношение р, полагая ири, если V можно получить из у с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований всех рассмотренных типов. Очевидно, р является отношением частичного порядка и для любого натурального п на множестве Атрь{п) С АТРЬ отношение р совпадает с ранее рассмотренным отношением >, так как из пит(и) = пит{у) и иру следует и > V. В силу этого отношение р далее будем обозначать через >.

Отношения !>, определенные нами на всех А¡РЬ(п), продолжим на АТРЬ, полагая и = (глх, гхг, • • •) ^ V = (^ъ • • •)> если щ + и2 + . + щ > VI + г>2 + • • • + VI (г — 1,2,.).

Отношение О, очевидно, является отношением частичного порядка на ИРЬ и его ограничение на любом АТРЬ{п) совпадает с >.

В третьем параграфе главы 1 установлено, что отношения > и !> совпадают на ИРЬ.

Второй основной результат главы 1 — следующая

Теорема 2. Мноэюество ЫРЬ является решеткой относительно отношения >.

Эту решетку мы будем называть решеткой разбиений натуральных чисел. Мы установим, что любая решетка АТРЬ(п) является подрешеткой решетки ИРЬ и решетка АТРЬ равна специальным образом устроенному дизъюнктному объединению таких подрешеток.

Устройство нижней части решетки ЫРЬ продемонстрировано на Рис. 2.

На множестве АТРЬ хорошо известны два других решеточных порядка — порядок Юнга, дающий решетку Юнга [38], и лексикографический порядок.

Пусть и = (и\, и2> • • = (VI, .) — два разбиения из АТРЬ. Порядок Юпга иУ V определяется условием щ > VI, и2 >У2,.

Очевидно, ИРЬ, является решеткой, которую называют решеткой Юнга. Из определения порядка Юнга следует щ + 42 + . + щ > VI + г>2 + • • - + VI {% — 1,2,.), т. е. введенный нами порядок > на ЫРЬ продолжает порядок Юнга.

Нетрудно заметить, что наш порядок на АТРЬ продолжается до лексикографического порядка.

Далее мы применим решетки ЫРЬ(п) для изучения хроматических многочленов графов. Собственно, изучение свойств хроматических многочленов графов и привело нас к идее рассмотрения указанных решеток. Мы уверены, что эти решетки будут полезны в различных исследованиях, где используются разбиения натуральных чисел и есть необходимость их сравнения. Вероятно, порядок > является наиболее естественным порядком для разбиений чисел.

Вторая глава посвящена новому подходу к изучению хроматической определяемости полных многодольных графов, основанному на использовании решеточного порядка, рассмотренного в главе 1.

В четвертом параграфе главы 2 мы исследуем свойства указанных ранее хроматических инвариантов относительно порядка > на множествах полных многодольных графов.

Пусть п — щ + П2 + . + nt, где щ > п2 > . > nt,> 1, — разбиение числа п. Через K(jii, П2,., тц) будем обозначать полный í-дольный граф на п вершинах с долями размеров Щ, П2, • ■ • 5 nt- Ясно, что с точностью до изоморфизма существует взаимно однозначное соответствие между полными í-дольными графами на п вершинах и элементами решетки NPL(n, t). Поэтому порядок < на NPL(n, t) индуцирует отвечающий ему порядок на множестве таких графов. Мы можем отождествлять полный многодольный n-граф с соответствующим разбиением числа п.

Пусть п и t — фиксированные натуральные числа, такие, что 3 < t < п. Разделим п на t с остатком: п — t • q + г, где О < г < t.

В 1982 г. Chao C.Y. и G.A. Novacky Jr. [35] доказали, что хроматически определяются полные t-дольные n-графы вида K(q + 1,., q + 1, q,., q), где компонента q + 1 повторяется г раз, а компонента q повторяется s = t — г раз. Иными словами, полные многодольные графы, являющиеся наименьшими элементами в решетках NPL(n,t), хроматически определяются. Далее мы приведем очень простое доказательство этого утверждения (см. Предложение 5.1).

Основной результат главы 2 — следующая

Теорема 3. Пусть {п\,п2,. ,nt) — разбиение, являющееся атомом решетки разбиений натурального числа п на t слагаемых, где rix > п2 > . > щ > 2 и t > 3. Тогда полный многодольный граф К(п\,п2, • ■ ■ ,щ) хроматически определяется.

Отметим, что частный случай теоремы при г = 0 был получен в 1988 г. Giudici R.E. и Lopez М.А. [36] (см. также (8) на стр. 5). Другой частный случай следует из результата Zhao Н.Х. [23] (см. также (12) на стр. 6), но при условии q > t + 2.

Третья глава посвящена изучению хроматической опреде-ляемости полных трехдольных графов, находящихся на нижних "этажах" решеток NPL(n,3). Основной результат главы 3 — следующая

Теорема 4. Пусть п — натуральное число и h — неотрицательное целое число < 3. Тогда любой полный трехдольный п-граф с неодноэлементными долями, имеющий высоту h в решетке NPL(n, 3), является хроматически определяемым.

Отметим, что данная теорема обобщает и усиливает ряд результатов, указанных на стр. 7. Возникающие здесь конкретные случаи описаны в главе 3.

1. Оре, О. Графы и их применение. — М.: Мир, 1965.

2. Оре, О. Теория графов и ее применения. — М.: Наука, 1980.Рейнгольд, Э., Нивергельт, Ю., Део, Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980.

3. Свами, М., Тхуласираман, К. Графы, сети и алгоритмы. — М.: Мир, 1984.

4. Татт, У. Теория графов. — М.: Мир, 1988.

5. Уилсон, Р. Введение в теорию графов. — М.: Мир, 1977.

6. Харари, Ф. Теория графов. — М.: Мир, 1973.

7. Birkhoft, G.D. A determinant formula for the number of ways of coloring a map // Annal. Math. 2nd Ser., 1912-1913. Vol. 14. P. 42-46.

8. Whitney, H. The coloring of graphs // Annal. Math., 1932. Vol. 33. P. 688-718.

9. Birkhoft, G.D., Lewis, D. Chromatic polynomials // Trans. Amer. Math. Soc., 1946. Vol. 60. P. 355-451.

10. Read, R.C. An introduction to chromatic polynomials //J. Comb. Theory, 1968. Vol. 4. P. 52-71.

11. Read, R.C., Tutte, W.T. Chromatic polynomials. — In: Selected Topics in Graph Theory III. Academic Press. 1988.

12. Koh, K.M., Teo, K.L. The search for chromatically unique graphs // Graphs Combin.,1990. Vol. 6 P. 259-285.

13. Koh, K.M., Teo, K.L. The search for chromatically unique graphs II // Discrete Math. 1997. Vol. 172. P. 59-78.

14. Chia, G.L. Some problems on chromatic polynomials // Discrete Math. 1997. Vol. 172. P. 39-44.

15. Liu, R.Y. Adjoint polynomials and chromatically unique graphs // Discrete Math. 1997. Vol. 172. P. 85-92.

16. Dong, F.M., Koh, K.M., Teo, K.L. Chromatic polynomials and chromaticity of graphs. — Monograph, Preprint, 2004.

17. Zhao, H. Chromaticity and adjoint polynomials of graphs. — Wöhrmann Print Service, The Netherlands, 2005.

18. Асанов, M.O., Баранский, В.А., Расин, B.B. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.

19. Farrell, E.J. On chromatic coefficients // Discrete Math. 1980. Vol. 29. P. 257-264.

20. Баранский, В.А., Вихарев, C.B. О хроматических инвариантах двудольных графов // Известия Уральского гос. университета, 2005. Математика и механика. Вып. 7. №36. С. 25-34.

21. Зыков, A.A. Теория конечных графов. — Новосибирск: Наука, 1969.

22. Зыков, A.A. Основы теории графов. — М.: Наука, 1987.

23. Chao, C.Y., E.G. Whitehead, Jr. On chromatic equivalence of graphs. In: Theory and applications of graphs (Proc. Internath. Conf., Western Mich. Univ., Kalamasoo, 1976). Lecture Notes in Math.,. Vol. 642, P. 121-131. -Springer, 1978.

24. Zou, H.W. The chromaticity of the complete tripartite graph К{п—А\щп) (Chinese) //J. Shanghai Teachers Univ. (Natur. Sei.) 1998. Vol. 1. P. 37-43.

25. Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph K(n — k\n\n) (Chinese) // J. Shanghai Teachers Univ. (Natural Sc.) 1999. Vol.1. P. 15-22.

26. Zou, H.W. The chromatic uniqueness of complete tripartite graphs K(n i; n2; n3) (Chinese) //J. Sys. Sei. Math. Sei. 2000. Vol. 20. P. 181-186.

27. Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph К{п]щп + k) (Chinese) //J. Shanghai Teachers Univ. (Natur. Sei.) 2000. Vol. 3. P. 29-35.

28. Zou, H.W. The chromatic uniqueness of certain complete tripartite graphs К(т\щг) // J. Math. (Wuhan) 2003. Vol. 23. P. 307-314.

29. Chao, C.Y., G.A. Novacky, Jr. On maximally saturated graphs // Discrete Math. 1982. Vol. 41. P. 139-143.

30. Giudici, R.E., Lopez, M.A. Chromatic uniqueness of sKn) Report No. 85-03, Dpto. de Mat. у Ciencia de la Comp. Univ. Sim.on Bolivar,1985

31. Li, N.Z., Liu, R.Y. The chromaticity of the complete t-partite graph K(l]p2]. ;pt) // J- Xinjiang Univ. Natur. Sei. 1990. Vol. 7. No.3. P. 95-96.

32. Айгнер, M. Комбинаторная теория. — M.: Мир, 1982.

33. Эндрюс, Г. Теория разбиений. — М.: Наука, 1982.

34. Гретцер, Г. Общая теория решеток. — М.: Мир, 1982.

35. Баранский, В.А., Королева, Т.А. Хроматическая определяемость атомов в решетках полных многодольных графов // Труды Института математики и механики УрО РАН. 2007. Том 13, №3. С. 22-29.

36. Королева, Т. А. Хроматическая определяемость некоторых полных трехдольных графов I // Труды Института математики и механики УрО РАН. 2007. Том 13, №3. С. 65-83.

37. Баранский, В.А., Королева, Т.А. Решетка разбиений натурального числа / / Доклады Академии Наук. 2008. Том 418, Ш. С. 439-442.

38. Королева, Т.А. О хроматической определяемости полных трехдольных графов // Труды XXXIX Молодежной конференции. ИММ УрО РАН, Екатеринбург 2008. С. 2327.

39. Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов // Сборник тезисов XV Международной конференции студентов, аспирантов и молодых ученых "Ломоносов-2008". С. 47.9