Авторефераты по всем темам  >>  Авторефераты по разным специальностям

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

УДК 519.174 Сеньчонок

Татьяна Александровна КЛАССИФИКАЦИЯ И ХРОМАТИЧЕСКАЯ ОПРЕДЕЛЯЕМОСТЬ ЭЛЕМЕНТОВ МАЛОЙ ВЫСОТЫ В РЕШЁТКАХ ПОЛНЫХ МНОГОДОЛЬНЫХ ГРАФОВ

01.01.06 - Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Екатеринбург - 2012

Работа выполнена на кафедре алгебры и дискретной математики Инн ститута математики и компьютерных наук ФГАОУ ВПО Уральский федеральный университет имени первого Президента России Б.Н. Ельн цина.

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

Официальные оппоненты: доктор физико-математических наук, профессор В.В. Кабанов кандидат физико-математических наук, доцент Е.А. Перминов

Ведущая организация: ФГБОУ ВПО Омский государственный университет им. Ф.М. Достоевского

Защита состоится л 22 мая 2012 года в 1400 на заседании диссерн тационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

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

Автореферат разослан л 18 апреля 2012 года Учёный секретарь диссертационного совета, кандидат физ.-мат. наук И.Н. Белоусов

Общая характеристика работы

Актуальность темы Изучение раскрасок графов началось с задачи о четырёх красках.

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

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

Особое место в исследовании хроматической определяемости гран фов занимает изучение полных многодольных графов, так как любая раскраска графа Ч это вложение этого графа в некоторый полный многодольный граф. То есть любой граф, раскрашиваемый в t цветов, можно получить из полного t-дольного графа удалением некоторого множества рёбер. Поэтому, опираясь на хроматические свойства полн ных многодольных графов, можно исследовать хроматическую опрен деляемость любых других классов графов. Полные t-дольные графы будем обозначать через K(n1, n2,..., nt), где n1, n2,..., nt Ч размеры всех t долей этого графа. Рассматривая полные t-дольные графы бун дем всегда предполагать, что n1 n2 ... nt.

В 1990 году Ли и Лью [11] доказали, что граф K(n1,..., nt-1, 1) является хроматически определяемым тогда и только тогда, когда 2 n1 ... nt-1 1. В силу этого в дальнейшем нас будет интересовать хроматическая определяемость полных многодольных графов только с неодноэлементными долями.

Задача о хроматической определяемости полных многодольных графов привлекала внимание значительного числа исследователей, при этом особым интересом пользовались случаи двух- и трёхдольных гран фов. Хроматической определяемости двудольных гафов было посвян щено множество работ, и, наконец, в 1990 году Кох и Тео [12] докан зали, что любой полный двудольный граф хроматически определяем, если его доли неодноэлементны. После этого задачи для двудольных графов фокусируются вокруг удаления из них определённых наборов рёбер и доказательства хроматической определяемости получившихся графов (см., например, [13]). Что же касается полных трёхдольных графов, то их хроматическая определяемость до сих пор не доказан на в общем случае, т. е. когда доли графа неодноэлементны. В настоян щее время продолжается исследование хроматической определяемости некоторых классов полных трёхдольных графов (см., например, [14]).

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

1. K(p, p,..., p, p - k) при k 2, t 4 и p k + 2 (Цао, 2005 [10]).

2. K(p, p,..., p, p - 1, p - k) при k 2, t 4 и p k + 2 (Ксю, 2008 [15]).

3. K(p,..., p, p - 1,..., p - 1, p - k) при p k + 2 4 и t d + 3 t-d-2 d+(Лау и Пенг, 2009 [16]).

В этих случаях авторы брали классы полных трёхдольных гран фов, хроматическая определяемость которых уже была доказана, и обобщали полученные результаты на произвольное число долей в гран фе. Заметим, что хроматическая определяемость этих полных многон дольных графов доказана в общем виде, т. е. в случае, когда доли гран фа неодноэлементны.

Другая часть исследований обращена к обобщению утверждения Чао и Новацки [17], которые в 1982 году доказали, что для любого t 2 полный t-дольный граф K(n1, n2,..., nt) хроматически опреден ляем, если |ni - nj| 1 для всех i, j = 1, 2,..., t. В этом направлении следует отметить результат Цао [10], он доказал, что если |ni - nj| и n1 n2 ... nt t + 1, то K(n1, n2,..., nt) хроматически определяем при t 2. Если обобщить задачу для произвольного знан чения |ni - nj| k (i, j = 1, 2,..., t), то ответ на этот вопрос дан ли Цао, Ли, Лью и Йе [18], они показали, что если |ni - nj| k и n1 n2 ... nt tk2/4 + 1 для некоторого натурального чисн ла k, то K(n1, n2,..., nt) хроматически определяем. В этих исследован ниях доказана хроматическая определяемость полных многодольных графов с серьёзным ограничением на размеры долей этих графов (nt достаточно велико).

Учитывая исследования различных авторов можно сформулирон вать следующую гипотезу: любой полный многодольный граф K(n1, n2,..., nt) является хроматически определяемым при n1 n2 ... nt 2.

Графы, хроматическую определяемость которых мы будем исслен довать, характеризуются своим положением в некоторой решётке полн ных t-дольных графов. Использовать решёточный порядок для докан зательства хроматической определяемости полных многодольных гран фов предложили Баранский и Королёва [19] в 2007 году. Хроматичен ская определяемость наименьшего элемента этих решёток была докан зана Чао и Новацки [17]. В работе [20] установлена хроматическая определяемость атомов этих решёток при nt 2. Элементы высоты и 3 этих решёток при t = 3 рассмотрены в работах [21Ц23], там же дон казана хроматическая определяемость полных трёхдольных графов, имеющих высоту 2 и 3 в решётках полных трёхдольных графов.

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

1. Дать классификацию элементов высоты 3 в решётках полных t-дольных графов при t 4.

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

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

Научная новизна Все результаты являются новыми.

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

Апробация работы Результаты диссертации были представлены на 42-й Всероссийн ской молодёжной школе-конференции (Екатеринбург, 2011), XIV Всен российской конференции УМатематическое программирование и прилон женияФ (Екатеринбург, 2011), на первом русско-финском симпозиуме по дискретной математике (Санкт-Петербург, 2011), Международной (43-й Всероссийской) молодёжной школе-конференции (Екатеринбург, 2012). Автор выступал с докладами по теме диссертации на семинаре УАлгебраические системыФ (УрФУ, рук. Л.Н. Шеврин, 2012) и на алн гебраическом семинаре института математики и механики УрО РАН (рук. А.А. Махнёв, 2012).

Публикации Материалы диссертации опубликованы в 8 печатных работах [27 - 34], из них 3 статьи в рецензируемых журналах [27Ц29] и 5 тезисов докладов [30Ц34]. 5 работ ([27], [29], [31Ц33]) опубликовано совместно с В.А. Баранским, однако доказательства основных результатов прин надлежат автору.

Структура и объём диссертации Диссертация состоит из введения, двух глав и списка литератун ры. Объём диссертации составляет 125 страниц. Библиографический список содержит 63 наименования.

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

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

Пусть G Ч произвольный (n, m, k)-граф, т. е. граф, имеющий n вершин, m рёбер и k компонент связности. Раскраской или t-раскраской графа G называется отображение из множества вершин V графа G в множество натуральных чисел {1, 2,..., t} такое, что для люн бых двух различных смежных вершин u и v графа G выполняется (u) = (v), т. е. любые две различные смежные вершины имеют разный УцветФ. Граф называется t-раскрашивае мым, если он обладан ет t-раскраской и Ч t-хро ма т ическим, если он t-раскрашиваемый, но не является (t - 1)-раскрашиваемым; в этом случае число t называют хро мати ческим чис ло м графа G и обозначают через (G).

Для натурального числа x через P (G, x) обозначим число всевозн можных раскрасок графа G в x заданных цветов, причём не предпон лагается, что в раскраске должны быть использованы все x цветов.

Хорошо известно, (см., например, [3] или [24]), что функция P (G, x) является многочленом степени n от переменной x, который называют хро мати ч е ским многочлено м графа G. Два графа называются хро ма н тически эквивалентными, если они имеют одинаковые хроматические многочлены.

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

Хроматическими инвариантами являются, например, число вершин, число рёбер и число компонент связности графа [3]. Число рёбер гран фа G будем обозначать через I2(G). Отметим, что число вершин графа G можно было бы обозначать через I1(G). Ещё одним хроматическим инвариантом является I3(G) Ч число треугольников в графе G [25].

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

x(i) = x(x - 1)(x - 2)... (x - i + 1), а через Ч хроматическое число графа G. В силу этой теоремы числа pt(G, i) при i n являютн ся хроматическими инвариантами. Нас особенно будут интересовать инварианты pt(G, ) и pt(G, + 1).

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

Граф G называют t-до ль ным графом, если множество его вершин можно разбить на t непустых подмножеств (долей) так, что любое ребн ро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина из одной доли соединена с кажн дой вершиной из других долей, то G называют по ным t-до льным графом и обозначают через K(n1, n2,..., nt), где n1, n2,..., nt Ч пон следовательность чисел элементов для всех t долей этого графа. Расн сматривая полные t-дольные графы будем всегда предполагать, что n1 n2 ... nt.

Разбиение м натурального числа n называется невозрастающая пон следовательность целых неотрицательных чисел u = (u1, u2,...) такая, что u1 u2 ..., причём u содержит лишь конечное число ненулен вых компонент и n = u1 + u2 +.... Число l такое, что l 1, ul > и ul+1 = ul+2 =... = 0, назовём длиной разбиения u, в этом случае будем писать u = (u1,..., ul).

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

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

Через NP L(n, t) обозначим множество всех разбиений длины t натурального числа n, где 1 t n. Определим понятие эле ментарн ного преобразования разбиения u = (u1, u2,..., ut) числа n [19]. Пусть натуральные числа i и j таковы, что 1) 1 i < j t;

2) ui - 1 ui+1 и uj-1 uj + 1;

3) ui = uj + , где 2.

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

Рассмотрим отношение на множестве NP L(n, t), полагая u v для u, v NP L(n, t), если v можно получить из u с помощью последон вательного выполнения конечного числа (возможно нулевого) элеменн тарных преобразований. Отметим, что NP L(n, t) является решёткой относительно [19].

Элементарное преобразование разбиения будем называть паденин е м блока, если j = i +1 и > 2 (см. Рис. 2(а)), и Ч сдвиго м блока, если i + 1 < j, ui = ui+1 + 1, ui+1 = ui+2 =... = uj-1 и uj-1 = uj + 1 (см.

Рис. 2(б)), или если j = i + 1 и = 2 (см. Рис. 2(в)).

(a) (б) (в) Рис. Рассмотрим отношение на NP L(n, t), полагая u v, если разн биение v получается из разбиения u падением или сдвигом блока. Отн метим, что отношение совпадает с отношением покрытия в решётке NP L(n, t) [19].

Пусть n = t q + r, где q Ч натуральное число и r Ч неотрицан тельное целое число такие, что 0 r < t. Нетрудно заметить, что разбиение (q + 1,..., q + 1, q,..., q), где число q + 1 повторяется r раз, а число q повторяется t - r раз, является наименьшим элементом рен шётки NP L(n, t).

Рассмотрим произвольный полный tЦдольный граф K(n1, n2,..., nt). Пусть n = n1 + n2 +... + nt Ч разбиение числа n, где n1 n2 ... nt 1. Очевидно, с точностью до изоморфизма существует взан имно однозначное соответствие между полными t-дольными графами на n вершинах и элементами решётки NP L(n, t). Поэтому мы можем отождествлять полный многодольный граф на n вершинах с соответн ствующим ему разбиением числа n. Конечно, порядок на NP L(n, t) можно рассматривать как порядок на множестве полных t-дольных графов на n вершинах.

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

В первом параграфе первой главы даны основные определения и сведения об объектах, используемых в тексте диссертации. Приведен ны леммы об изменении значений хроматических инвариантов I2(G), I3(G) и pt(G, + 1) при выполнении элементарных преобразований.

Во втором параграфе первой главы получена классификация элементов высоты 3 в решётках NP L(n, t) при t 4. Результаты этой классификации сформулированы в виде Теоремы 1. В этой теорен ме представлена таблица, в которой перечислены все элементы высоты 3 и условия их существования, а также некоторые их числовые хан рактеристики. В частности, в колонке УВысотаФ указана высота этих элементов в решётке NP L(n, t), т. е. длина кратчайшего пути в решётн ке от наименьшего элемента до представленного. В колонке УУровеньФ мы указали разницу в количестве рёбер между наименьшим элеменн том и рассматриваемым. Отметим, что в тексте диссертации вместо Теоремы 1 представлено более общее утверждение Ч Теорема 1.1, кон торая нам необходима при доказательстве второго нашего основного результата.

Теорема 1. Следующая таблица дает классификацию эле ментов вын соты 3 в решётка х NP L(n, t) при t 4.

Таблица 1. Элементы малой высоты в решётках NP L(n, t) при t а Условие Элемент существования Высот Уровень b1 = (q + 1,..., q + 1, q,..., q) 0 r t - 1 0 r t-r b2 = (q + 2, q + 1,..., q + 1, q,..., q) 2 r t - 1 1 r-2 t-r+b3 = (q + 1,..., q + 1, q,..., q, q - 1) 0 r t - 2 1 r+1 t-r-b4 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q) 4 r t - 1 2 r-4 t-r+b5 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1) 1 r t - 1 2 r-1 t-r-b6 = (q + 1,..., q + 1, q,..., q, q - 1, q - 1) 0 r t - 4 2 r+2 t-r-3 = r t - 1 2 b7 = (q + 3, q + 1,..., q + 1, q,..., q) 4 r t - 1 3 r-3 t-r+b8 = (q + 2,..., q + 2, q + 1,..., q + 1, q,..., q) 6 r t - 1 3 3 r-6 t-r+b9 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q, q - 1) 3 r t - 1 3 r-3 t-r b10 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1, q - 1) 0 r t - 3 3 r t-r-b11 = (q + 1,..., q + 1, q,..., q, q - 1,..., q - 1) 0 r t - 6 3 r+3 t-r-6 0 r = t - 3 2 b12 = (q + 1,..., q + 1, q,..., q, q - 2) 0 r t - 4 3 r+2 t-r-2 = r t - 1 3 b14 = (q + 3, q + 1,..., q + 1, q,..., q, q - 1) 3 = r t - 1 3 r-2 t-r b17 = (q+2,q+2, q+1,...,q+1, q,...,q, q-1,q-1) 2 = r < t = 4 3 r-2 t-r-b19 = (q + 2, q + 1,..., q + 1, q,..., q, q - 2) 1 r = t - 2 3 0 r = t - 3 3 r t-r-В третьем параграфе первой главы указаны основные виды чан стично упорядоченных множеств, представляющих нижние этажи рен шёток NP L(n, t) для различных значений n и t. Вид решётки NP L(n, t) будет существенным образом зависеть от значений и соотношения пан раметров r и t. При достаточно больших значениях r и t (в некотон ром наиболее общем случае) элементы высоты 3 имеют в решётке NP L(n, t) уровень 3. Это происходит при условии 6 r t - 6, и в этом случае нижние этажи решётки NP L(n, t) выглядят как пон казано на Рис. 3. Отметим, что на Рис. 3 над символами покрытий представлены числа, на которые изменяется инвариант pt(G, t + 1).

b7 = (q + 3, q + 1,..., q + 1, q,..., q) r-3 t-r+b8 = (q + 2,..., q + 2, q + 1,..., q + 1, q,..., q) 3 r-6 t-r+b4 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q) r-4 t-r+b2 = (q + 2, q + 1,..., q + 1, q,..., q) b9 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q, q - 1) r-2 t-r+1 r-3 t-r b1 = (q + 1,..., q + 1, q,..., q) b5 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1) r t-r r-1 t-r-b3 = (q + 1,..., q + 1, q,..., q, q - 1) b10 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1, q - 1) r+1 t-r-2 r t-r-b6 = (q + 1,..., q + 1, q,..., q, q - 1, q - 1) r+2 t-r-b11 = (q + 1,..., q + 1, q,..., q, q - 1,..., q - 1) r+3 t-r-6 b12 = (q + 1,..., q + 1, q,..., q, q - 2) r+2 t-r-Рис. q q q q q q q q q q q q q q В некоторых частных случаях элементы высоты 3 в решётках NP L(n, t) могут иметь уровень 4. Например, при условии 3 = r t-нижние 4 этажа решётки NP L(n, t) будут выглядеть следующим обн разом (Рис. 4).

c1 = b7 = (q + 3, q + 1,..., q + 1, q,..., q) r-3 t-r+b14 = (q + 3, q + 1,..., q + 1, q,..., q, q - 1) r-2 t-r b2 = (q + 2, q + 1,..., q + 1, q,..., q) b9 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q, q - 1) r-2 t-r+1 r-3 t-r b1 = (q + 1,..., q + 1, q,..., q) b5 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1) b17 = (q+2,q+2, q+1,...,q+1, q,...,q, q-1,q-1) r t-r r-1 t-r-1 r-2 t-r-b3 = (q + 1,..., q + 1, q,..., q, q - 1) b10 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1, q - 1) r+1 t-r-2 r t-r-b6 = (q + 1,..., q + 1, q,..., q, q - 1, q - 1) b18 = (q+2, q+1,..., q+1, q,..., q, q-1,..., q-1) r+2 t-r-4 r+1 t-r-5 b11 = (q + 1,..., q + 1, q,..., q, q - 1,..., q - 1) r+3 t-r-6 b20 = (q + 1,..., q + 1, q,..., q, q - 1,..., q - 1) r+4 t-r-8 b19 = (q + 2, q + 1,..., q + 1, q,..., q, q - 2) r t-r-b12 = (q + 1,..., q + 1, q,..., q, q - 2) r+2 t-r-b21 = (q + 1,..., q + 1, q,..., q, q - 1, q - 2) r+3 t-r-Рис. q q q q q q q q q q q q q q q q q q q q q q При условии 8 r = t-3 получаем симметричный предыдущему вид нижних четырёх уровней решётки NP L(n, t) (Рис. 5).

b13 = (q + 3, q + 2, q + 1,..., q + 1, q,..., q) r-5 t-r+b7 = (q + 3, q + 1,..., q + 1, q,..., q) r-3 t-r+b14 = (q + 3, q + 1,..., q + 1, q,..., q, q - 1) r-2 t-r b15 = (q + 2,..., q + 2, q + 1,..., q + 1, q,..., q) 4 r-8 t-r+b8 = (q + 2,..., q + 2, q + 1,..., q + 1, q,..., q) 3 r-6 t-r+b4 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q) b16 = (q+2,..., q+2, q+1,..., q+1, q,..., q, q-1) r-4 t-r+2 3 r-5 t-r+b2 = (q + 2, q + 1,..., q + 1, q,..., q) b9 = (q + 2, q + 2, q + 1,..., q + 1, q,..., q, q - 1) r-2 t-r+1 r-3 t-r b1 = (q + 1,..., q + 1, q,..., q) b5 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1) b17 = (q+2,q+2, q+1,...,q+1, q,...,q, q-1,q-1) r t-r r-1 t-r-1 r-2 t-r-b3 = (q + 1,..., q + 1, q,..., q, q - 1) b10 = (q + 2, q + 1,..., q + 1, q,..., q, q - 1, q - 1) r+1 t-r-2 r t-r-b19 = (q + 2, q + 1,..., q + 1, q,..., q, q - 2) r t-r-c2 = b12 = (q + 1,..., q + 1, q,..., q, q - 2) r+2 t-r-Рис. Для всех остальных значений параметров r и t нижние этажи сон ответствующей решётки NP L(n, t) будут вкладываться естественным q q q q q q q q q q q q q q q q q q q q q q образом как частично упорядоченное множество в одну из трёх прин ведённых выше решёток. Полученные изображения нижних этажей решёток NP L(n, t) будут полезны нам в дальнейшем при доказательн стве хроматической определяемости элементов этих решёток.

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

В первом параграфе второй главы приведена схема доказательн ства хроматической определяемости интересующих нас полных мнон годольных графов. При выполнении элементарного преобразования инвариант I2 (число рёбер в соответствующем графе) увеличиваетн ся. Для доказательства хроматической определяемости графа G = K(n1, n2,..., nt) рассматривается соответствующее ему разбиение u = (n1, n2,..., nt) в решётке NP L(n, t), при этом граф G можно обознан чить через K(u). Пусть граф H хроматически эквивалентен графу K(u). Если H = K(v), то элементы u и v находятся на одном уровне решётки NP L(n, t), так как I2(G) = I2(H). Если же H = K(v) - E для некоторого множества рёбер E графа K(v), то элемент v будет нан ходиться k уровнями ниже u в решётке NP L(n, t), где k = |E|. Таким образом, для доказательства хроматической определяемости некотон рого полного многодольного графа достаточно показать, что он хрон матически не эквивалентен ни одному графу, находящемуся с ним на одном уровне в решётке NP L(n, t), и что, удаляя ребра из элеменн тов меньшего уровня в решётке, нельзя получить граф, хроматически эквивалентный данному. Хроматическую неэквивалентность графов мы часто показываем, сравнивая значения инвариантов pt(G, + 1) соответствующих графов. Для этого нами получена оценка изменен ния этого инварианта при удалении рёбер из графа, а именно, k pt(H, + 1) - pt(G, + 1) 2k - 1. Отметим, что наибольшую сложн ность при доказательствах вызывает случай nt = 2. Причина этой сложности заключается в том, что при малых значениях некоторых из чисел n1, n2,..., nt разность pt(H, + 1) - pt(G, + 1) вычисляется довольно сложным образом. В первом параграфе второй главы нами фактически указан метод вычисления данной разности, что открын вает, по нашему мнению, хорошую перспективу для подтверждения сформулированной гипотезы в общем виде.

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

Теорема 2. Пусть n и t Ч натуральные чис ла такие, что t < n.

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

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

В работах [10], [15] и [16] рассмотрен элемент b12, элемент b5 при условии r = t - 1 и элемент b19 при условии r = t - 2.

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

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

Список литературы [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] Read, R.C., Tutte, W.T. Chromatic polynomials // Selected Topics in Graph Theory III. Academic Press. 1988. P. 15Ц42.

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

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

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

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

[10] Zhao, H. Chromaticity and adjoint polynomials of graphs. Zutphen:

W ohrmann Print Service, 2005. 169 p.

[11] Li, N.Z., Liu, R.Y. The chromaticity of the complete tЦpartite graph K(1; p2;..; pt) // Xinjiang Univ. Natur. Sci. 1990. Vol. 7, № 3.

P. 95Ц96.

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

[13] Rolsan, H., Peng, Y.H. Chromatic uniqueness of complete bipartite graphs with certain edges deleted // Ars Combin. 2011.

Vol. 98. P. 203Ц213.

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

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

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

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

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

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

С. 439Ц442.

[20] Баранский, В.А., Королева, Т.А. Хроматическая определян емость атомов в решетках полных многодольных графов // Тр.

Ин-та математики и механики УрО РАН. 2007. Т. 13, № 3. С. 22Ц29.

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

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

С. 39Ц56.

[23] Баранский, В.А., Королева, Т.А. Хроматическая определяен мость некоторых полных трехдольных графов // Изв. Урал. гос.

ун-та. 2010. № 74. С. 5Ц26.

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

368 с.

[25] Farrell, E.J. On chromatic coe cients // Discrete Math. 1980.

Vol. 29. P. 257Ц264.

[26] Зыков, А.А. Основы теории графов. М.: УВузовская книгаФ, 2004.

664 с.

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

С. 159Ц173.

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

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

Т. 17, № 4. С. 3Ц18.

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

Институт математики и механики УрО РАН. 2011. С. 241Ц243.

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

[32] Баранский, В.А., Сеньчонок, Т.А. Хроматическая определян емость элементов высоты 3 в решетках полных многодольных графов // Тезисы Международной конференции по алгебре и геон метрии, посвящённой 80-летию со дня рождения А.И.Старостина.

Екатеринбург: Изд-во УУМЦ-УПИФ. 2011. С. 16Ц17.

[33] Baransky, V.A., Senchonok, T.A. 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.

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

Авторефераты по всем темам  >>  Авторефераты по разным специальностям