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

• Сеньчонок, Татьяна Александровна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Сеньчонок, Татьяна Александровна

Содержание

Введение

Глава 1. Описание элементов высоты < 3 в решётках ЫРЬ(п,1)

1.1. Решётки КРЬ(п,Ь) и хроматические инварианты

1.2. Классификация элементов высоты 2 и 3 в решётках ИРЬ(п,1)

1.3. Нижние этажи решёток МРЬ(п^)

Глава 2. Хроматическая определяемость элементов высоты < 3 в решётках NРЪ(п,1)

2.1. Раскраски графов и свойства хроматических инвариантов

2.2. Хроматическая определяемость элементов высоты 2 в решётках ИРЦп^)

2.3. Хроматическая определяемость элементов высоты 3 в решётках ЫРЦп^)

Литература

Введение диссертации (часть автореферата) на тему «Классификация и хроматическая определяемость элементов малой высоты в решётках полных многодольных графов»

Введение

Изучение раскрасок графов началось с задачи о четырёх красках. В 1852 году Гутри предложил выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. В терминах графов эта задача звучит так: показать, что хроматическое число плоского графа (карты) не превосходит четырёх. При попытках доказательства этого факта в 1912 году Биркгоф [1] ввёл понятие хроматического многочлена карты.

Понятие хроматического многочлена в 1932 году было обобщено Уитни [2] на произвольный граф. Им же было найдено несколько фундаментальных свойств таких многочленов. В 1968 году Рид [3] ввёл понятие хроматически эквивалентных графов, т. е. графов, имеющих одинаковые хроматические многочлены, и сформулировал задачу о необходимых и достаточных условиях хроматической эквивалентности графов. В 1978 году Чао и Уайтхед [4] ввели понятие хроматически определяемого графа, т. е. графа, который определяется своим хроматическим многочленом с точностью до изоморфизма. Они же нашли некоторые семейства хроматически определяемых графов [5-7]. Хотя Биркгоф и не смог решить проблему четырёх красок с помощью хроматических многочленов, его исследования породили в теории раскрасок графов множество работ других авторов по хроматической эквивалентности и хроматической определяемости графов. Данное направление активно развивается и в настоящее время.

Теория раскрасок графов имеет огромное практическое значение. Она используется для задач теории расписаний, задач распараллеливания численных методов, задач экономии памяти, задач распределения ресурсов, технологий цифровых водяных знаков и многих других задач (см. [8-17]). Что

же касается исследований, связанных с хроматическими многочленами, то они стали весьма разнообразными и обширными. Состояние дел в этой области достаточно полно изложено в обзорных статьях [18-22] и монографиях [23, 24].

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

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

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

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

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

антами являются число вершин, число рёбер и число компонент связности графа [3]. Число рёбер графа С будем обозначать через /2(С). Отметим, что число вершин графа С можно было бы обозначать через 1\{0). Ещё одним хроматическим инвариантом является /з(С?) — число треугольников в графе С (см. [26] или [27]).

Далее через pt(G, г) мы будем обозначать число разбиений множества вершин графа (У на г непустых коклик, т. е. подмножеств, состоящих из попарно несмежных вершин графа По теореме Зыкова (см. [28] или [29])

п г=Х

где через х^ обозначается факториальная степень переменной х, т. е. х^ = х(х — 1)(х — 2)... (х — г + 1), а через х ~ хроматическое число графа (7. В силу этой теоремы числа г) при % < г < п являются хроматическими инвариантами. Нас особенно будут интересовать инварианты х) и

рКС,Х + !)•

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

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

ЧТО П1 > П2 > ... > Щ.

Все полные графы Кп хроматически определяемы (только их хроматические многочлены имеют вид х^). Возникает естественный вопрос: если из Кп начать удалять рёбра, останутся ли полученные графы хроматически определяемыми? В частности, какие из полных ¿-дольных графов К(п\,п2,... ,щ) будут х-определяемы? Лоренц и Уайтхед в 1981 году [30] изучали класс графов, полученных из Кп удалением множества из к (0 < 2к < п) независимых рёбер, т. е. паросочетания из к рёбер. Они показали, что все такие графы хроматически определяемы. Ясно, что каждый их этих графов изоморфен некоторому графу К{пъп2,..., щ), где ¿>2и1<Пг<2 для всех г = 1, 2,..., Более общий результат относительно таких графов получили Чао и Новацкий в 1982 году [31]. Они доказали, что для любого £ > 2 граф К{п1,П2, хроматически определяем, если \щ — < 1 для всех г,= 1,2,... , Отметим, что этот результат легко вытекает из теоремы Турана (см. Бонди и Мурти [32]), так как рассматриваемый граф — это граф, имеющий максимальный размер (по числу рёбер) среди всех графов на п = щ + щ Н-----Ь щ

вершинах, имеющих хроматическое число равное

Задача о хроматической определяемости полных многодольных графов привлекала внимание значительного числа исследователей, при этом особым интересом пользовался случай двух- и трёхдольных графов. Хроматической определяемости двудольных гафов были посвящены работы [33, 34], ив 1990 году Кох и Тео [19] доказали, что полный двудольный граф К(п1,П2) хроматически определяем при щ > щ > 2. После этого задачи для двудольных графов фокусируются вокруг удаления из них определённых наборов рёбер и доказательства хроматической определяемости получившихся графов [35-38]. Что же касается полных трёхдольных графов К(п\, п2, Пз), то их хроматическая определяемость до сих пор не доказана в общем случае при Щ > П2 > щ > 2. В настоящее время продолжается исследование хромати-

ческой определяемости для некоторых классов полных трёхдольных графов [39-44].

Многие же исследования направлены на произвольные полные t-дольные графы. Часть исследований, по аналогии с трёхдольными графами, касается доказательства хроматической определяемости полных t-дольных графов определённого вида. Доказано, что хроматически определяемы следующие многодольные графы.

1. К(р,р,... ,р,р - к) при к > 2, t > 4 и р > к + 2 (Цао, 2005 [24]).

2. К(р,р,... ,р,р - 1,р - к) при к > 2, t > 4 и р > к + 2 (Ксю, 2008 [45]).

t-d-2 d+1 Пенг, 2009 [46]).

Другая часть исследований обращена к обобщению утверждения Чао и Новацки [31]. В связи с этим Кох и Тео поставили задачу: будет ли граф K(m,n2,..., щ) хроматически определяем, если \щ — rij\ <2 для всех i,j = 1,2, и число nt достаточно велико, где щ > щ > ... > щ! В 1985 году Гьюдичи и Лопез [47] доказали, что полные t-дольные графы K(q 41, q,..., g, q — 1) хроматически определяемы при t > 2 и q > 3. Более общий ответ на поставленный вопрос получил Цао [24], он доказал, что если |щ — rij\ < 2 и ni > Щ > ... > щ > t + 1, то K(ni,ri2,... ,nt) хроматически определяем при t > 2. Если обобщить задачу для произвольного значения \щ — rij| < к (г, j — 1, 2,..., t), то ответ на этот вопрос дали Цао, Ли, Лью и Йе [48], они показали, что если \щ — щ\ < к и щ > П2 > ... > щ > tk2/4 -Ь 1 для некоторого натурального числа к, то K(ni,ri2,... ,щ) хроматически определяем. Отметим, что Цао ранее получил аналогичный результат [24], но с оценкой для щ, которая хуже указанной здесь.

к) при p>k + 2>4w.t>d + 3>3 (Лау и

В 1990 г. Ли и Лью [49] доказали, что граф К(п\,... 1) является ^-определяемым тогда и только тогда, когда 2 > п\ > ... > \ > 1.

В ходе исследований различных авторов возникла следующая гипотеза: любой полный многодольный граф ■ ■ ■ является хрома-

тически определяемым при щ > п2 > ... > щ > 2.

Графы, хроматическую определяемость которых мы будем доказывать, характеризуются своим положением в некоторой решётке разбиений натуральных чисел. Основы теории разбиений чисел были заложены Эйлером ещё в XVIII веке. В монографии [50] приведены сведения по истории этой теории и многочисленным её достижениям.

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

и = (щ,и2,...) = (иъ...,щ).

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

Рис. 1

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

Через ЫРЬ{п, ¿) обозначим множество всех разбиений длины £ натурального числа п, где 1 < £ < п. Определим понятие элементарного преобразования разбиения и = (-¿¿х, гл2,. •. ,щ) числа п — пит(и) [51]. Пусть натуральные числа г и у таковы, что

1) 1 < г < з < Ц

2) щ — 1 > щ+1 и щ-г + 1;

3) щ = г^- + (), где 5 >2.

Будем говорить, что разбиение г> = (^1,..., щ — 1,..., щ + 1,..., щ) получено элементарным преобразованием (или перекидыванием блока) разбиения и = (щ,... щ), и будем писать в этом случае и -> V. Отметим,

что г; отличается от и точно на двух компонентах с номерами гну. Для диаграммы Ферре такое преобразование означает перемещение верхнего блока г-го столбца вправо в ^'-ый столбец. Условия 2) и 3) гарантируют, что после такого перемещения снова получится диаграмма Ферре.

Рассмотрим отношение > на множестве АГРЬ(п, £) [51], полагая и > V для и,у £ ИРЬ(п, £), если и можно получить из и с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований. Ясно, что отношение > на множестве МРЬ(п, ¿) является отношением частичного порядка. Отметим, что выполняется

тогда и только тогда, когда щ + .. .+щ > г>1 + .. .+Vi для любого г = 1,2,..., Отметим, что МРЬ(п, £) является решёткой относительно > [51].

Элементарное преобразование разбиения будем называть падением блока, если ; = г + 1 и 5 > 2 (см. Рис. 2(а)), и — сдвигом блока, если i + 1 < ^ щ — щ+1 + 1, г/г-+1 = = ... = и = % 1 (см. Рис. 2(6)), или если ;=г + 1и5 = 2 (см. Рис. 2(в)).

1

-1

(а)

(б) Рис. 2

(в)

Рассмотрим отношение => на ЫРЬ{п, ¿), полагая и V, если разбиение V получается из разбиения и падением или сдвигом блока. Отметим, что отношение совпадает с отношением покрытия в решётке МРЬ(п, ¿) [51].

Пусть п = £ • q + г, где д — натуральное число и г — неотрицательное целое число такие, что 0 < г < ¿. Нетрудно заметить, что разбиение (д + 1,..., д-Ь 1, д,..., д), где число д +1 повторяется г раз, а число д повторяется £ — г раз, является наименьшим элементом решётки ЛГР£(п,£).

Рассмотрим произвольный полный ¿-дольный граф К{п\, П2, ■ • •, щ)-Пусть п — щ + П2 + ... 4- щ — разбиение числа п, где щ > П2 > ... > щ > 1. Очевидно, с точностью до изоморфизма существует взаимно однозначное соответствие между полными ¿-дольными графами на п вершинах и элементами решётки АТРЬ(п,£). Поэтому мы можем отождествлять полный многодольный граф на п вершинах с соответствующим ему разбиением числа п. Конечно, порядок > на АТРЬ{п^) можно рассматривать как порядок на множестве полных ¿-дольных графов на п вершинах.

Как уже говорилось, в работе [31] доказано, что хроматически определяемы полные ¿-дольные графы вида К{д + 1,..., д + 1, д,..., д). Иными словами, хроматически определяемы полные многодольные графы, являющиеся наименьшими элементами в решётках ЛГР£(п, ¿). В работе [52] установлена хроматическая определяемость атомов в решётках ЫРЬ{п^ ¿) при щ > 2. Элементы высоты 2 и 3 этих решёток при ¿ = 3 рассмотрены в работах [53-55], там же доказана хроматическая определяемость полных трёхдольных графов, имеющих высоту 2 и 3 в решётках АТРЬ(п, 3) при щ > 2.

Цели данной работы состоят в следующем.

1. Дать классификацию элементов высоты < 3 в решётках АТРЬ(п, £) разбиений натуральных чисел п заданной длины I при £ > 4.

2. Исследовать хроматическую определяемость полных многодольных графов с неодноэлементными долями, имеющих высоту < 3 в этих решётках.

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

Первая глава посвящена классификации элементов высоты < 3 в решётках разбиений натуральных чисел заданной длины Ь > 4.

В первом параграфе первой главы даны основные определения и сведения об объектах, используемых в тексте диссертации. Сформулированы и доказаны леммы об изменении значений хроматических инвариантов/2(С), /3(С) и х + 1) при выполнении элементарных преобразований.

Во втором параграфе первой главы получена классификация элементов высоты < 3 в решётках А/"РЬ(п, при £ > 4. Результаты этой классификации сформулированы в виде Теоремы 1. В этой теореме представлена таблица, в которой перечислены все элементы высоты < 3 и условия их существования, а также некоторые их числовые характеристики. В частности, в колонке "Высота" указана высота этих элементов в решётке МРЬ(п,£), т.е. длина кратчайшего пути в решётке от наименьшего элемента до представленного. В колонке "Уровень" мы указали разницу в количестве рёбер между наименьшим элементом и рассматриваемым. Отметим, что далее в тексте диссертации вместо Теоремы 1 представлено более общее утверждение — Теорема 1.1, которая нам понадобится при доказательстве второго нашего основного результата.

Теорема 1. Следующая таблица дает классификацию элементов высоты < 3 в решётках ЛТРЬ(п, £) при £ > 4.

Таблица 1. Элементы малой высоты в решётках ЫРЬ(п,1) при г > 4

Элемент Условие существования Высота Уровень

Ь\ = ($ + 1,...,д + 1,^,...,^) г Ь—г о < г < г - 1 0 0

Ь2 = (д + 2чд + 1,...,д + 1—2 ¿-г+1 2 < г < £ — 1 1 1

63 = (д + 1,-..,д+ 1чд,...,д^,д- 1) г+1 г-г-2 0 < г < £ — 2 1 1

64 = (д + 2,д + 2чд + 1,...,д + 1чд,...,ду) г-4 £-г+2 4 < г<1 2 2

65 = (д + 2чд + 1,...,д+1чд,...,д^,д-1) г—1 г—1 1 < г < £ - 1 2 2

Ь6 = + 1,...,д + 1чд,...,д^,д- 1,д - 1) г+2 ¿-г-4 0 < г < £ — 4 2 2

Ь7 = (д + Зчд-1- 1,...,д + 1чд,...,ду) г-З £-г+2 3 = г < £ — 1 2 3

4 < г < £ - 1 3 3

Ь8 = (д + 2,...,д + 2чд + 1,...,д+ 1,чд,...,дЗ 3 т—б ¿-г+З 6 < г < £ - 1 3 3

69 = (д + 2,д + 2чд + 1,...,д + 1чд,...,д/д- 1) г-З ¿-г 3 < г <г-1 3 3

Ью = (д + 2чд + 1,-., д + 1, % д - 1, д - 1) г Ь—г—3 0<г<£-3 3 3

6ц = (чд + 1,...,д + 1чд,...,д^чд- 1,...,д- 1) г+З ¿-г-6 3 0 < г <6 3 3

Продолжение на следующей странице

Элемент Условие существования Высота Уровень

Ь\2 = (# + + 1, 2) г+2 г-г-ъ о < г = г - з 2 3

о < г < г - 4 3 3

Ьы = (д + + + 1, 1) г—2 ¿-г 2=г<г-\ 3 4

з = г < Ь - 1 3 4

&17 = (д + 2,д + 2чд + 1,...,д + 1,д- 1) г—2 ¿-г-2 2 = г < £ = 4 3 4

&19 = (д + + 1,..., д + 1,^,..., д-2) г Ь-г-2 1 <г = £_2 3 4

0 < г = £ — 3 3 4

В третьем параграфе первой главы указаны основные виды частично упорядоченных множеств, представляющих нижние этажи решёток АтРЬ(п, для различных значений п и Так как п = д • £ -Ь г, вид решётки ЫРЬ(п, ¿) будет существенным образом зависеть от значений и соотношения параметров ги1 При достаточно больших значениях г и £ (в некотором наиболее общем случае) элементы высоты <3 имеют в решётке ЫРЬ{п, £) уровень <3. Это происходит при условии 6 < г < £ — 6, ив этом случае нижние этажи решётки АТРЬ{п^) выглядят как показано на Рис. 3. Отметим, что на Рис. 3 над символами покрытий представлены числа, на которые изменяется инвариант £ + 1).

Ь7 = (<? + 3, д + 1,..., 9 + 1, д,..., д)

г-3 4-Г+2

Ь8 = (д + 2,...,д + 2,д + 1,...,д + 1,д,...,д)

г—б г+3

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

л - Лч

г—4 4-Г+2

Ь2 = (д + 2, <7 + 1,..., д + 1,9,..., 9) Ь9 = (9 + 2,9 + 2,9 + 1,...,9 + 1,9,..., 9, д - 1)

г-2 4-г+1\

Ьх = (9 + 1,..., 9 + 1,9,..., 9) Ь5 = (9 + 2,9 + 1,..., 9 + 1,9,..., 9,9 - 1)

г-3 4-г

Г Л ¿ — г \

г-1 4-Г-1

Ьз = (д + 1,...,9 + - 1) Ью = (9 + 2,9 + 1,..., 9 + 1,9,..., 9,9 - 1,9 - 1)

4-г-З

Ьб = (9 + 1,...,9 + 1,9,..., 9,9 - 1,9-1)

г+20 *-г-4

Ьц = (9 + 1,..., 9 + 1,9,...,9, 9 - 1,...,9 - 1)

г+З 4-Г--6

Ь12 = + 1,-, 9 + 1, Ч ~ 2)

г+2 4-г-З

Рис. 3

В некоторых частных случаях элементы высоты 3 в решётках ЛГРЬ(п, £) могут иметь уровень 4. Например, при условии 3 = г < £ — 8 нижние 4 этажа решётки Л/"Р1/(п, будут выглядеть следующим образом (Рис. 4).

С1 = Ьт = (д + 3,д + 1,...,д + 1,д,...,д)

39.

7—з г-г+2

Ь14 = (д + 3,д + 1, <?,..., 1)

г —2 Ь-г

Ь2 = (д + 2,д+1,.„,д+1,д,...,д) Ь9 = (д + 2, д + 2, д + 1,. д + 1, д , д, д - 1)

г-з г-т

1—2 1-Г+1

Ьх = (д + 1,...,д + 1,д,...,д) Ь5 = (д + 2, д + 1,..., д + 1, д,.,., д, д - 1) Ь17 = (д + 2, д + 2, д + 1,..., д + 1, д,..., д, д - 1,9 - 1)

{-г

(д + 2,_д + 1,...,д + 1,^д,д-2)

£—7—2

Ь21 = (д + 1,..., д + 1, д,-., д,д - 1,д - 2)

г+З ¡-1—5

Рис. 4

При условии 8 < г = Ь — 3 получаем симметричный предыдущему вид нижних четырёх уровней решётки iVPL(n, (Рис. 5).

Ьхз = (д + 3,д + 2,д+ 1,...,д + 1,д,...,д)

Ь4 = (9 + 2,9 + 2,9 + 1,..., 9 + 1, 9/.., 9) Ьхе = (9 + 2,..., д + 2, д + 1,..., 9 + 1, 9,..., 9,9 - 1)

/ >

Ь2 = (9 + 2,9+ 1,..., 9+ 1,9,...,9) Ь9 = (9 + 2,9 + 2,9 + 1,..., 9 + 1,9,..., 9,9 - 1)

1—2 *-г+1

г-з г-т

Ьх = (9+ 1,...,9+ 1, 9,..., 9) Ь5 = (9 + 2, 9 + 1,..., 9 + 1, 9,..., 9, д - 1) Ьх7 = (9 + 2, д + 2, 9 + 1,..., д + 1, д, 9 - 1,д - 1)

г-2 г-г-2

г+1 4-?—2

Ьхэ = (д + 2,9 + 1, 9 + 1, д,„., 9, д - 2)

г (-?—2

С2 = Ьх2 = (д + 1,...,д+ 1,9,..., д, 9 - 2)

г+2 Ь — г—З

Рис. 5

Для всех остальных значений параметров г и £ нижние этажи соответствующей решётки МРЬ(п, £) будут вкладываться естественным образом как частично упорядоченное множество в одну из трёх приведённых выше решёток. Полученные изображения нижних этажей решёток ЫРЬ{п, £) будут по-

лезны нам в дальнейшем при доказательстве хроматической определяемости элементов этих решёток.

Вторая глава диссертации посвящена доказательству хроматической определяемости полных многодольных графов, имеющих высоту 2 и 3 в решётках NPL(n:t).

В первом параграфе второй главы приведена схема доказательства хроматической определяемости интересующих нас полных многодольных графов. При выполнении элементарного преобразования инвариант /2 (число ребер в соответствующем графе) увеличивается, это видно из увеличения уровня элементов при возрастании высоты. Для доказательства хроматической определяемости графа G = Я"(ni, 712,... ,nt) рассмотрим соответствующее ему разбиение и = (ni,n2,. • • в решётке NPL(n,t), при этом граф G можно обозначить через К (и). Пусть граф H хроматически эквивалентен графу К (и). Если H = K(v), то элементы и и v находятся на одном уровне решётки NPL(n,t), так как h{G) = h{H)- Если же H — K(v) — Е для некоторого множества рёбер Е графа K(v), то элемент v будет находиться к уровнями ниже и в решётке NPL(n,t), где к = \Е\. Таким образом, для доказательства хроматической определяемости некоторого полного многодольного графа достаточно показать, что он хроматически не эквивалентен ни одному графу, находящемуся с ним на одном уровне в решётке NPL(n,t), и что, удаляя ребра из элементов меньшего уровня в решётке, нельзя получить граф, х-эквивалентный данному. Хроматическую неэквивалентность графов мы будем часто показывать, сравнивая значения инвариантов pt(G, х + 1) соответствующих графов. Для этого нами получена оценка изменения этого инварианта при удалении рёбер из графа, а именно, к < pt(H, х + 1) — vK^i Х +1) < 2fc —1. Отметим, что наибольшую сложность при доказательствах вызывает случай щ = 2. Причина этой сложности заключается в том, что при малых значениях некоторых из чисел ni, П2,... ,nt

разность pt(H, х+1)— pt(G, х+1) вычисляется довольно сложным образом. В параграфе 2.1 нами фактически указан метод вычисления данной разности, что открывает, по нашему мнению, хорошую перспективу для подтверждения сформулированной гипотезы в общем виде.

Во втором и третьем параграфах второй главы доказывается хроматическая определяемость полных многодольных графов, имеющих в решётке NPL(n,t) высоту 2 и 3, соответственно. Результатом этой главы является следующая

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

Соотнесём результаты, полученные нами, с результатами предшествующих исследований.

1. Цао доказал [24] хроматическую определяемость графов вида К (и) — К(р,р,... ,р,р — к) при к >2, £>4ир>/с + 2.

Если к = 2, то при g = р — 1 имеем и — (g + 1,..., g + 1, q — 1) — это элемент 63 при г = t — 2 и высота элемента h — 1.

Если к = 3, то при q — р — 1 имеем и = (q + 1,..., q + 1, q — 2) — это элемент 612 при г = t — 3h/i = 2.

Если к — 4, то при q — р — 1 имеем и = (q+1,..., 1, q — 3), элементов такого вида нет в Таблице 1, значит его высота h > 4.

Если к > 5, то тем более h > 4.

2. Ксю доказал [45] хроматическую определяемость графов вида К(р,р,... — — к) при к >2, £>4ир>& + 2.

Если к = 2, то при q = р — 1 имеем и = (g + 1,..., g + 1, g, g — 1) — это элемент 63 при г = t — 3 и высота элемента h = 1.

Если к = 3, то при q = р — 1 имеем и = (д + 1,..., д + 1, д, д — 2) — это элемент 612 при г = t — 4 и /1 = 2.

Если А; = 4, то при д = р — 1 имеем г/ = (д + 1,..., д + 1, д, д — 3). Если £ > 5, имеем /г > 4.

Если £ = 4, то при д! = д — 1 имеем п = (дх + 2, д! 4- 2, д! + 1, дх — 2). Здесь г = 3 и Н > 4.

Если & > 5, то /г > 4.

3. Jlay и Пенг доказали [46] хроматическую определяемость графов вида

t—d—2 d+1

t-d-2>(d + 3)-d-2 = lTid+l>l.

Если к — 2, то при g = р — 1 имеем w = (g + 1,..., д + 1, д,..., д, д — 1) — это атом 63.

Если к = 3, то при д = р — 1 имеем и = (д + 1,..., д + 1, д,..., д, д — 2).

4 V У

t—d—2

Если £ — d — 2 > 2, то это 612 при t — d — 2 = г + 2и d+1 = £ — г — 3, т. е. r = £ — d — 4<£ — 4и/г = 3.

Если t — d — 2 — 1, то при gi = д — 1 получаем элемент

u = (gi + 2, gi + 1,... ,gi 4-1, gi - 1) — это 65 при r = t — lnh = 2.

d+1>1

Если к = 4, то при q = р— 1 имеем и — (g 4- 1, • • •,д + 1,д,...,д,д — 3).

i—d—2>1 d+l>l

Если £ - d - 2 > 3, то h > 4.

Если t — d — 2 — 2, то при gi = д — 1 получаем элемент

n = (gi + 2, gi + 2, gi 4-1,..., gi + 1, gi - 2), значит h > 4 (здесь г = t - 1).

d+l>l

Если t — d — 2 = 1, то при gi = q — 1 получаем элемент

гх = (gi + 2, gx + 1,..., gi 4-1, gi - 2) — это &i9 при r = t- 2nh = 3.

d+l>l

Если к > 5, то h > 4.

Как мы видим, в работах [24, 45] и [46] рассмотрен элемент 612, элемент 65 при условии г — t — 1 и элемент 619 при условии г = t — 2.

Что касается результата Цао, Ли, Лью и Йе [48], в случае элементов высоты 2 и 3 мы улучшили оценку щ > tk2/4 + 1 до оптимальной оценки Щ > 2.

Список литературы диссертационного исследования кандидат физико-математических наук Сеньчонок, Татьяна Александровна, 2012 год

Литература

[1] Birkhoff, 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.

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

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

[4] Chao, C.Y., Whitehead Jr., E.G. On chromatic equivalence of graphs // Theory and Appl. of Graphs. 1978. Vol. 642. P. 121-131.

[5] Chao, C.Y., Whitehead Jr., E.G. Chromaticity of self-complementary graphs // Arch. Math. (Basel) 1979. Vol. 32. P. 295-304.

[6] Chao, C.Y., Whitehead Jr., E.G. Chromatically unique graphs // Discrete Math. 1979. Vol. 27. P. 171-177.

[7] Chao, C.Y., Zhao, L.C. Chromatic polynomials of a family of graphs // Ars Combin. 1983. Vol. 15. P. 111-129.

[8] Берж, К. Теория графов и ее применения. — М.: Иностранная литература, 1962. 320 с.

[9] Евстигнеев, В.А. Применение теории графов в программировании. — М.: Наука, 1985. 352 с.

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

[11] Оре, О. Графы и их применение. — М.: Мир, 1965. 175 с.

12] Ope, О. Теория графов. — М.: Наука, 1980. 340 с.

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

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

15] Татт, У. Теория графов. - М.: Мир, 1988. 306 с.

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

17] Харари, Ф. Теория графов. - М.: Едиториал УРСС, 2003. 296 с.

18] Read, R.C., Tutte, W.T. Chromatic polynomials // Selected Topics in Graph Theory III. Academic Press. 1988. P. 15-42.

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

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

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

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

23] Dong, F.M., Koh, K.M., Teo, K.L. Chromatic polynomials and chromaticity of graphs. — Monograph, Preprint, 2004. 356 p.

24] Zhao, H. Chromaticity and adjoint polynomials of graphs. — Zutphen: Wöhrmann Print Service, 2005. 169 p.

[25] Асанов, М.О., Баранский, В.А., Расин, В.В. Дискретная математика: графы, матроиды, алгоритмы. — СПб.: Издательство "Лань", 2010. 368 с.

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

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

[28] Зыков, А.А. Теория конечных графов. — Новосибирск: Наука, 1969. 543 с.

[29] Зыков, А.А. Основы теории графов. — М.: "Вузовская книга", 2004. 664 с.

[30] Loernic, В., Whitehead Jr., E.G. Chromatic polynomials for regular graphs and modified wheels //J. Combin. Theory Ser. B. 1981. Vol. 31, Ne 1. P. 54-61.

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

[32] Bondy, J.A., Murty, U.S.R. Graph theory with applications. — New York: American Elsevier Publishing Co., Inc., 1976. 654 p.

[33] Salzberg, P.M., Lopez, M.A., Giudici, R.E. On the chromatic uniqueness of bipartite graphs // Discrete Math. 1986. Vol. 3. P. 285-294.

[34] Tomescu, I. On 3-colorings of bipartite p-threshold graphs //J. Graph Theory. 1987. Vol. 11. P. 327-338.

[35] Chia, G.L., Ho, C.K. On the chromatic uniqueness of edge-gluing of complete bipartite graphs and cycles // Ars Combin. 2001. Vol. 60. P. 193-199.

[36] Zou, H.W. Chromatic uniqueness of certain bipartite graphs K(m,n) — A(\A\ > 2) (Chinese) // Tongji Daxue Xuebao Ziran Kexue Ban. 2002. Vol. 8. P. 1014-1018.

[37] Peng, Y.H., Rolsan, H. Chromatic uniqueness of certain bipartite graphs with six edges deleted // Thai J. Math. 2010. Vol. 8, № 2. P. 339-354.

[38] Rolsan, H., Peng, Y.H. Chromatic uniqueness of complete bipartite graphs with certain edges deleted // Ars Combin. 2011. Vol. 98. P. 203-213.

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

[40] 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.

[41] Zou, H.W. The chromatic uniqueness of complete tripartite graphs K(m]n2;n3) (Chinese) // J. Sys. Sci. Math. Sci. 2000. Vol. 20. P. 181-186.

[42] 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.

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

[44] Su, K.Y., Chen, X.E. A note on chromatic uniqueness of completely tripartite graphs //J. Math. Res. Exposition 2010. Vol. 30, № 2. P. 233-240.

[45] Xu, L.M. Chromatic uniqueness of complete ¿-partite graphs K(n — k, n,..., n) (Chinese) // J. Univ. Sci. Technol. China 2010. Vol. 38, № 9. P. 1036-1041.

[46] Lau, G.C., Peng, Y.H. Chromatic uniqueness of certain complete ¿-partite graphs // Ars Combin. 2009. Vol. 92. P. 353-376.

[47] Giudici, R.E., Lopez, M.A., Salzberg, P.M. Chromatic uniqueness for some bipartite graphs Кт^п (Spanish) // Acta Cient. Venezolana 1986. Vol. 37. P. 484-494.

[48] Zhao, H.X., Li, X.L., Liu, R.Y., Ye, C.F. The chromaticity of certain complete multipartite graphs // Graphs and Combin. 2004. Vol. 20. P. 423-434.

[49] Li, N.Z., Liu, R.Y. The chromaticity of the complete ¿-partite graph K{l-p2] ..-,pt) Ц Xinjiang Univ. Natur. Sci. 1990. Vol. 7, № 3. P. 95-96.

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

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

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

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

[54] Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов. II // Изв. Урал. гос. ун-та. 2010. № 74. С. 39-56.

[55] Баранский, В.А., Королева, Т.А. Хроматическая определяемость некоторых полных трехдольных графов // Изв. Урал. гос. ун-та. 2010. № 74. С. 5-26.

[56] Сеньчонок, Т. А. О хроматической определяемости элементов высоты 2 в решётках полных многодольных графов // Тезисы 42-й Всероссийской молодежной школы-конференции. — Екатеринбург: Институт математики и механики УрО РАН. 2011. С. 241-243.

[57] Баранский, В.А., Сеньчонок, Т.А. О хроматической определяемости элементов малой высоты в решетках полных многодольных графов // XIV Всероссийская конференция Математическое программирование и приложения (тезисы докладов). — Екатеринбург: УрО РАН. 2011. С. 150-151.

[58] Сеньчонок, Т.А., Баранский, В.А. Классификация элементов малой высоты в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 2. С. 159-173.

[59] Баранский, В.А., Сеньчонок, Т.А. Хроматическая определяемость элементов высоты <3 в решетках полных многодольных графов // Тезисы Международной конференции по алгебре и геометрии, посвящён-ной 80-летию со дня рождения А.И.Старостина. — Екатеринбург: Изд-во "УМЦ-УПИ". 2011. С. 16-17.

[60] Сеньчонок, Т.А. Хроматическая определяемость элементов высоты 2 в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 3. С. 271-281.

[61] Baransky, V.A., Senchonok, Т.А. Chromatic uniqueness of elements of height <3 in lattices of complete multipartite graphs // First Russian-

Finnish Symposium on Discrete Mathematics. Abstracts. — St.Petersburg. 2011. P. 13-14.

[62] Баранский, В.А., Сеньчонок, Т.А. Хроматическая определяемость элементов высоты <3 в решетках полных многодольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 3-18.

[63] Сеньчонок, Т. А. О свойствах хроматического инварианта pt(G, х + 1) // Тезисы Международной (43-й Всероссийской) молодежной школы-конференции. — Екатеринбург: Институт математики и механики УрО РАН. 2012. С. 84-86.