WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

УДК 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.




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.