close

Вход

Забыли?

вход по аккаунту

?

Классификация и хроматическая определяемость элементов малой высоты в решетках полных многодольных графов

код для вставкиСкачать
ФИО соискателя: Сеньчонок Татьяна Александровна Шифр научной специальности: 01.01.06 - математическая логика, алгебра и теория чисел Шифр диссертационного совета: Д 004.006.03 Название организации: Институт математики и механики УрО РАН Адрес органи
На правах рукописи
УДК 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].
Особое место в исследовании хроматической определяемости гра­
фов занимает изучение полных многодольных графов, так как любая
раскраска графа — это вложение этого графа в некоторый полный
многодольный граф. То есть любой граф, раскрашиваемый в  цветов,
можно получить из полного -дольного графа удалением некоторого
множества рёбер. Поэтому, опираясь на хроматические свойства пол­
ных многодольных графов, можно исследовать хроматическую опре­
деляемость любых других классов графов. Полные -дольные графы
будем обозначать через (1 , 2 , . . . ,  ), где 1 , 2 , . . . ,  — размеры
3
всех  долей этого графа. Рассматривая полные -дольные графы бу­
дем всегда предполагать, что 1 ≥ 2 ≥ ... ≥  .
В 1990 году Ли и Лью [11] доказали, что граф (1 , . . . , −1 , 1)
является хроматически определяемым тогда и только тогда, когда 2 ≥
1 ≥ ... ≥ −1 ≥ 1. В силу этого в дальнейшем нас будет интересовать
хроматическая определяемость полных многодольных графов только
с неодноэлементными долями.
Задача о хроматической определяемости полных многодольных
графов привлекала внимание значительного числа исследователей, при
этом особым интересом пользовались случаи двух- и трёхдольных гра­
фов. Хроматической определяемости двудольных гафов было посвя­
щено множество работ, и, наконец, в 1990 году Кох и Тео [12] дока­
зали, что любой полный двудольный граф хроматически определяем,
если его доли неодноэлементны. После этого задачи для двудольных
графов фокусируются вокруг удаления из них определённых наборов
рёбер и доказательства хроматической определяемости получившихся
графов (см., например, [13]). Что же касается полных трёхдольных
графов, то их хроматическая определяемость до сих пор не доказа­
на в общем случае, т. е. когда доли графа неодноэлементны. В настоя­
щее время продолжается исследование хроматической определяемости
некоторых классов полных трёхдольных графов (см., например, [14]).
Многие же исследования направлены на произвольные полные
-дольные графы. В них можно выделить два основных направления
исследований. Часть исследований, по аналогии с трёхдольными гра­
фами, касается доказательства хроматической определяемости пол­
ных -дольных графов определённого вида. Доказано, что хромати­
чески определяемы следующие многодольные графы.
1. (, , . . . , ,  − ) при  ≥ 2,  ≥ 4 и  ≥  + 2 (Цао, 2005 [10]).
2. (, , . . . , ,  − 1,  − ) при  ≥ 2,  ≥ 4 и  ≥  + 2 (Ксю,
2008 [15]).
3. (,..., ,  − 1,...,  − 1,  − ) при  ≥  + 2 ≥ 4 и  ≥  + 3 ≥ 3
−−2
+1
(Лау и Пенг, 2009 [16]).
В этих случаях авторы брали классы полных трёхдольных гра­
фов, хроматическая определяемость которых уже была доказана, и
4
обобщали полученные результаты на произвольное число долей в гра­
фе. Заметим, что хроматическая определяемость этих полных много­
дольных графов доказана в общем виде, т. е. в случае, когда доли гра­
фа неодноэлементны.
Другая часть исследований обращена к обобщению утверждения
Чао и Новацки [17], которые в 1982 году доказали, что для любого
 ≥ 2 полный -дольный граф (1 , 2 , . . . ,  ) хроматически опреде­
ляем, если | −  | ≤ 1 для всех ,  = 1, 2, . . . , . В этом направлении
следует отметить результат Цао [10], он доказал, что если | −  | ≤ 2
и 1 ≥ 2 ≥ ... ≥  ≥  + 1, то (1 , 2 , . . . ,  ) хроматически
определяем при  ≥ 2. Если обобщить задачу для произвольного зна­
чения | −  | ≤  (,  = 1, 2, . . . , ), то ответ на этот вопрос да­
ли Цао, Ли, Лью и Йе [18], они показали, что если | −  | ≤  и
1 ≥ 2 ≥ ... ≥  ≥  2 /4 + 1 для некоторого натурального чис­
ла  , то (1 , 2 , . . . ,  ) хроматически определяем. В этих исследова­
ниях доказана хроматическая определяемость полных многодольных
графов с серьёзным ограничением на размеры долей этих графов (
достаточно велико).
Учитывая исследования различных авторов можно сформулиро­
вать следующую гипотезу: любой полный многодольный граф
(1 , 2 , . . . ,  ) является хроматически определяемым при 1 ≥ 2 ≥
... ≥  ≥ 2.
Графы, хроматическую определяемость которых мы будем иссле­
довать, характеризуются своим положением в некоторой решётке пол­
ных -дольных графов. Использовать решёточный порядок для дока­
зательства хроматической определяемости полных многодольных гра­
фов предложили Баранский и Королёва [19] в 2007 году. Хроматиче­
ская определяемость наименьшего элемента этих решёток была дока­
зана Чао и Новацки [17]. В работе [20] установлена хроматическая
определяемость атомов этих решёток при  ≥ 2. Элементы высоты 2
и 3 этих решёток при  = 3 рассмотрены в работах [21–23], там же до­
казана хроматическая определяемость полных трёхдольных графов,
имеющих высоту 2 и 3 в решётках полных трёхдольных графов.
Цели работы состоят в следующем:
1. Дать классификацию элементов высоты ≤ 3 в решётках полных
-дольных графов при  ≥ 4.
2. Доказать хроматическую определяемость полных многодольных
5
графов с неодноэлементными долями, имеющих высоту ≤ 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 наименования.
6
Содержание работы
Во введении описывается история вопроса хроматической опре­
деляемости графов, даётся обзор наиболее содержательных результа­
тов, полученных в данной предметной области, а также вводятся ба­
зовые определения и обозначения, необходимые для формулировки и
понимания результатов диссертации. Воспроизведём здесь определе­
ния основных понятий.
В данной работе мы рассматриваем только обыкновенные графы,
т. е. графы без петель и кратных рёбер. Обозначения и терминологию
для графов будем использовать в соответствии с [24].
Пусть  — произвольный (, , )-граф, т. е. граф, имеющий 
вершин,  рёбер и  компонент связности.
или 
графа  называется отображение  из множества вершин  графа
 в множество натуральных чисел {1, 2, . . . , } такое, что для лю­
бых двух различных смежных вершин  и  графа  выполняется
() ̸= (), т. е. любые две различные смежные вершины имеют
разный “цвет”. Граф называется 
, если он облада­
ет -раскраской и — 
, если он -раскрашиваемый, но
не является ( − 1)-раскрашиваемым; в этом случае число  называют
графа  и обозначают через ().
Для натурального числа  через  (, ) обозначим число всевоз­
можных раскрасок графа  в  заданных цветов, причём не предпо­
лагается, что в раскраске должны быть использованы все  цветов.
Хорошо известно, (см., например, [3] или [24]), что функция  (, )
является многочленом степени  от переменной , который называют
графа . Два графа называются
, если они имеют одинаковые хроматические
многочлены.
Предположим, что каждому графу приписано некоторым обра­
зом число. Это число называют
, если
оно одинаково для любых двух хроматически эквивалентных графов.
Хроматическими инвариантами являются, например, число вершин,
число рёбер и число компонент связности графа [3]. Число рёбер гра­
фа  будем обозначать через 2 (). Отметим, что число вершин графа
 можно было бы обозначать через 1 (). Ещё одним хроматическим
инвариантом является 3 () — число треугольников в графе  [25].
Далее через (, ) мы будем обозначать число разбиений множе­
ства вершин графа  на  непустых
, т. е. подмножеств, состоя­
Раскраской
-раскраской
-раскрашиваемым
-хроматическим
хроматическим числом
хроматическим многочленом
тически эквивалентными
хрома­
хроматическим инвариантом
коклик
7
щих из попарно несмежных вершин графа . По теореме Зыкова [26]
хроматический многочлен можно представить в виде
 (, ) =

∑︁
(, )() ,
=
где через () обозначается
факториальная степень переменной , т. е.
 = ( − 1)( − 2) . . . ( −  + 1), а через  — хроматическое число
графа . В силу этой теоремы числа (, ) при  ≤  ≤  являют­
ся хроматическими инвариантами. Нас особенно будут интересовать
инварианты (, ) и (,  + 1).
Граф является
, если он изоморфен
любому хроматически эквивалентному ему графу.
Граф  называют 
графом, если множество его вершин
можно разбить на  непустых подмножеств (долей) так, что любое реб­
ро данного графа соединяет вершину из одной доли с вершиной из
другой доли; если каждая вершина из одной доли соединена с каж­
дой вершиной из других долей, то  называют

графом и обозначают через (1 , 2 , . . . ,  ), где 1 , 2 , . . . ,  — по­
следовательность чисел элементов для всех  долей этого графа. Рас­
сматривая полные -дольные графы будем всегда предполагать, что
1 ≥ 2 ≥ ... ≥  .
натурального числа  называется невозрастающая по­
следовательность целых неотрицательных чисел  = (1 , 2 , . . .) такая,
что 1 ≥ 2 ≥ . . ., причём  содержит лишь конечное число ненуле­
вых компонент и  = 1 + 2 + . . .. Число  такое, что  ≥ 1,  > 0
и +1 = +2 = . . . = 0, назовём
разбиения , в этом случае
будем писать  = (1 , . . . ,  ).
Разбиение натурального числа удобно изображать в виде так на­
зываемой
, которую можно представить в виде вер­
тикальной стенки, сложенной из кубических блоков одинакового раз­
мера. Вот пример такой диаграммы.
()
хроматически определяемым
-дольным
полным -дольным
Разбиением
длиной
диаграммы Ферре
Рис. 1
8
На Рис. 1 представлено разбиение 20 = 6 + 4 + 4 + 3 + 1 + 1 + 1
числа 20 на 7 слагаемых. Здесь 7 — длина разбиения (6, 4, 4, 3, 1, 1, 1).
Через   (, ) обозначим множество всех разбиений длины 
натурального числа , где 1 ≤  ≤ . Определим понятие
разбиения  = (1 , 2 , . . . ,  ) числа  [19]. Пусть
натуральные числа  и  таковы, что
1) 1 ≤  <  ≤ ;
2)  − 1 ≥ +1 и −1 ≥  + 1;
3)  =  +  , где  ≥ 2.
Будем говорить, что разбиение  = (1 , . . . ,  − 1, . . . ,  + 1, . . . ,  )
получено элементарным преобразованием (или
) разбиения  = (1 , . . . ,  , . . . ,  , . . . ,  ). Отметим, что  отлича­
ется от  точно на двух компонентах с номерами  и  . Для диаграммы
Ферре такое преобразование означает перемещение верхнего блока -го
столбца вправо в  -ый столбец. Условия 2) и 3) гарантируют, что после
такого перемещения снова получится диаграмма Ферре.
Рассмотрим отношение ≥ на множестве   (, ), полагая  ≥ 
для ,  ∈   (, ), если  можно получить из  с помощью последо­
вательного выполнения конечного числа (возможно нулевого) элемен­
тарных преобразований. Отметим, что   (, ) является решёткой
относительно ≥ [19].
Элементарное преобразование разбиения будем называть
, если  =  + 1 и  > 2 (см. Рис. 2(а)), и —
, если
 + 1 <  ,  = +1 + 1, +1 = +2 = . . . = −1 и −1 =  + 1 (см.
Рис. 2(б)), или если  =  + 1 и  = 2 (см. Рис. 2(в)).
элементар­
ного преобразования
перекидыванием бло­
ка
падени­
сдвигом блока
ем блока
(a)
(б)
(в)
Рис. 2
Рассмотрим отношение ⇒ на   (, ), полагая  ⇒  , если раз­
биение  получается из разбиения  падением или сдвигом блока. От­
метим, что отношение ⇒ совпадает с отношением покрытия в решётке
  (, ) [19].
Пусть  =  ·  + , где  — натуральное число и  — неотрица­
тельное целое число такие, что 0 ≤  < . Нетрудно заметить, что
9
разбиение ( + 1, . . . ,  + 1, , . . . , ), где число  + 1 повторяется  раз,
а число  повторяется  −  раз, является наименьшим элементом ре­
шётки   (, ).
Рассмотрим произвольный полный –дольный граф (1 , 2 , . . . ,
 ). Пусть  = 1 + 2 + . . . +  — разбиение числа , где 1 ≥ 2 ≥
. . . ≥  ≥ 1. Очевидно, с точностью до изоморфизма существует вза­
имно однозначное соответствие между полными -дольными графами
на  вершинах и элементами решётки   (, ). Поэтому мы можем
отождествлять полный многодольный граф на  вершинах с соответ­
ствующим ему разбиением числа . Конечно, порядок ≥ на   (, )
можно рассматривать как порядок на множестве полных -дольных
графов на  вершинах.
Первая глава диссертации посвящена классификации элементов
высоты ≤ 3 в решётках разбиений натуральных чисел заданной длины
 ≥ 4.
В первом параграфе первой главы даны основные определения
и сведения об объектах, используемых в тексте диссертации. Приведе­
ны леммы об изменении значений хроматических инвариантов 2 (),
3 () и (,  + 1) при выполнении элементарных преобразований.
Во втором параграфе первой главы получена классификация
элементов высоты ≤ 3 в решётках   (, ) при  ≥ 4. Результаты
этой классификации сформулированы в виде Теоремы 1. В этой теоре­
ме представлена таблица, в которой перечислены все элементы высоты
≤ 3 и условия их существования, а также некоторые их числовые ха­
рактеристики. В частности, в колонке “Высота” указана высота этих
элементов в решётке   (, ), т. е. длина кратчайшего пути в решёт­
ке от наименьшего элемента до представленного. В колонке “Уровень”
мы указали разницу в количестве рёбер между наименьшим элемен­
том и рассматриваемым. Отметим, что в тексте диссертации вместо
Теоремы 1 представлено более общее утверждение — Теорема 1.1, ко­
торая нам необходима при доказательстве второго нашего основного
результата.
Следующая таблица дает классификацию элементов вы­
соты ≤ 3 в решётках   (, ) при  ≥ 4.
Теорема 1.
10
Условие
существования
Уровень
Элементы малой высоты в решётках   (, ) при  ≥ 4
Высота
Таблица 1.
1 = ( + 1,...,  + 1, ,...,  )
0≤ ≤−1
0
0
2 = ( + 2,  + 1,...,  + 1, ,...,  )
2≤ ≤−1
1
1
3 = ( + 1,...,  + 1, ,...,  ,  − 1)
0≤ ≤−2
1
1
4 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  )
4≤ ≤−1
2
2
5 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1)
1≤ ≤−1
2
2
6 = ( + 1,...,  + 1, ,...,  ,  − 1,  − 1)
0≤ ≤−4
2
2
7 = ( + 3,  + 1,...,  + 1, ,...,  )
3= ≤−1
4≤ ≤−1
2
3
3
3
8 = ( + 2,...,  + 2,  + 1,...,  + 1, ,...,  )
6≤ ≤−1
3
3
9 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  ,  − 1)
3≤ ≤−1
3
3
10 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1,  − 1)
0≤ ≤−3
3
3
11 = ( + 1,...,  + 1, ,...,  ,  − 1,...,  − 1)
0≤ ≤−6
3
3
0≤ =−3
0≤ ≤−4
2= ≤−1
3= ≤−1
2
3
3
3
3
3
4
4
17 = (+2,+2, +1,...,+1, ,..., , −1,−1)
2=<=4
3
4
1≤ =−2
0≤ =−3
3
3
4
4
Элемент

−
−2
+1
−+1
−−2
−4
−1
+2
−+2
−−1
−−4
−3
−+2
3
−6
−+3
−
−3

+3
−−3
−−6
3
12 = ( + 1,...,  + 1, ,...,  ,  − 2)
+2
−−3
14 = ( + 3,  + 1,...,  + 1, ,...,  ,  − 1)
−
−2
−2
−−2
19 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 2)

−−2
11
В третьем параграфе первой главы указаны основные виды ча­
стично упорядоченных множеств, представляющих нижние этажи ре­
шёток   (, ) для различных значений  и . Вид решётки   (, )
будет существенным образом зависеть от значений и соотношения па­
раметров  и . При достаточно больших значениях  и  (в некото­
ром наиболее общем случае) элементы высоты ≤3 имеют в решётке
  (, ) уровень ≤3. Это происходит при условии 6 ≤  ≤  − 6,
и в этом случае нижние этажи решётки   (, ) выглядят как по­
казано на Рис. 3. Отметим, что на Рис. 3 над символами покрытий
представлены числа, на которые изменяется инвариант (,  + 1).
b7 = ( + 3,  + 1,...,  + 1, ,...,  )
−+2
2
−3
b8 = ( + 2,...,  + 2,  + 1,...,  + 1, ,...,  )
−
3
1
−6
−+3
2
−
1
2
1
−
2
b4 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  )
−4
−+2
2  −2
b2 = ( + 2,  + 1,...,  + 1, ,...,  ) b9 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  ,  − 1)
−
−+1 1
−3
2 −−2
−
2
2
b1 = ( + 1,...,  + 1, ,...,  )
 2
−
−2
−
2
1
b5 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1)
−−1
2 −−1
2
b3 = ( + 1,...,  + 1, ,...,  ,  − 1) b10 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1,  − 1)

+12 
−−2
−−3
1
−2
−

2
b6 = ( + 1,...,  + 1, ,...,  ,  − 1,  − 1)
+22 
−−4
−2
3
−
2
b11 = ( + 1,...,  + 1, ,...,  ,  − 1,...,  − 1)
+3
−−6
b12 = ( + 1,...,  + 1, ,...,  ,  − 2)
+2
Рис. 3
12
−−3
3
В некоторых частных случаях элементы высоты 3 в решётках
  (, ) могут иметь уровень 4. Например, при условии 3 =  ≤ −8
нижние 4 этажа решётки   (, ) будут выглядеть следующим об­
разом (Рис. 4).
c1 = b7 = ( + 3,  + 1,...,  + 1, ,...,  )
2 −
−3
−+2
2
b14 = ( + 3,  + 1,...,  + 1, ,...,  ,  − 1)
−
2
3
·2 
−
1
−2
b9 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  ,  − 1)
b2 = ( + 2,  + 1,...,  + 1, ,...,  )
2 −
1
−2
2 −
2
−+1
2 −
1
−
−
−3
2
2
b1 = ( + 1,...,  + 1, ,...,  ) b5 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1) b17 = (+2,+2, +1,...,+1, ,..., , −1,−1)

2
−
2
−
1
−
−1
2 −
−−2
−−2
2
b10 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1,  − 1)

−−3
2 −
1
−
2
−2
1
−
2
b3 = ( + 1,...,  + 1, ,...,  ,  − 1)
+1
−−1
2 −
2
2
2
b6 = ( + 1,...,  + 1, ,...,  ,  − 1,  − 1) b18 = (+2, +1,..., +1, ,...,  , −1,..., −1)
+2
2 −
−−4
+1
1
−
−−5
3
2
2
b11 = ( + 1,...,  + 1, ,...,  ,  − 1,...,  − 1)
+3
2 −
−−6
3
2
3
−
2
b20 = ( + 1,...,  + 1, ,...,  ,  − 1,...,  − 1)
2
−−8
4
3
−
3
−
2
+4
b19 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 2)

1
−
−−2
2
b12 = ( + 1,...,  + 1, ,...,  ,  − 2)
+2
2 −
−−3
2
b21 = ( + 1,...,  + 1, ,...,  ,  − 1,  − 2)
+3
Рис. 4
13
−−5
При условии 8 ≤  =  − 3 получаем симметричный предыдущему
вид нижних четырёх уровней решётки   (, ) (Рис. 5).
b13 = ( + 3,  + 2,  + 1,...,  + 1, ,...,  )
−5
1
−
−+3
2
b7 = ( + 3,  + 1,...,  + 1, ,...,  )
−3
−+2
2 −
2
b14 = ( + 3,  + 1,...,  + 1, ,...,  ,  − 1)
−
2
2
−2
2
b15 = ( + 2,...,  + 2,  + 1,...,  + 1, ,...,  )
4
1
−
−8
−+4
2
b8 = ( + 2,...,  + 2,  + 1,...,  + 1, ,...,  )
3
1
−
2 −
2
−6
−+3
2
b4 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  ) b16 = (+2,..., +2, +1,..., +1, ,...,  , −1)
2 −
1
−
2
−2
2 −
2
1
−+2
1
−
−+1
3
−5
−+1
2
b9 = ( + 2,  + 2,  + 1,...,  + 1, ,...,  ,  − 1)
b2 = ( + 2,  + 1,...,  + 1, ,...,  )
2 −
−4
2
2 −
1
−
−
−3
2
2
b1 = ( + 1,...,  + 1, ,...,  ) b5 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1) b17 = (+2,+2, +1,...,+1, ,..., , −1,−1)

2
−
2
−
1
−
−1
2 −
b3 = ( + 1,...,  + 1, ,...,  ,  − 1)
+1
−−1
2
2
−−2
−2
1
−
−−2
2
b10 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 1,  − 1)

−−3
3
−
2
3
3
−
·2
b19 = ( + 2,  + 1,...,  + 1, ,...,  ,  − 2)

1
−
−−2
2
c2 = b12 = ( + 1,...,  + 1, ,...,  ,  − 2)
+2
−−3
Рис. 5
Для всех остальных значений параметров  и  нижние этажи со­
ответствующей решётки   (, ) будут вкладываться естественным
14
образом как частично упорядоченное множество в одну из трёх при­
ведённых выше решёток. Полученные изображения нижних этажей
решёток   (, ) будут полезны нам в дальнейшем при доказатель­
стве хроматической определяемости элементов этих решёток.
Вторая глава диссертации посвящена доказательству хромати­
ческой определяемости полных многодольных графов, имеющих высо­
ту 2 и 3 в решётках   (, ).
В первом параграфе второй главы приведена схема доказатель­
ства хроматической определяемости интересующих нас полных мно­
годольных графов. При выполнении элементарного преобразования
инвариант 2 (число рёбер в соответствующем графе) увеличивает­
ся. Для доказательства хроматической определяемости графа  =
(1 , 2 , . . . ,  ) рассматривается соответствующее ему разбиение  =
(1 , 2 , . . . ,  ) в решётке   (, ), при этом граф  можно обозна­
чить через (). Пусть граф  хроматически эквивалентен графу
(). Если  = (), то элементы  и  находятся на одном уровне
решётки   (, ), так как 2 () = 2 (). Если же  = () − 
для некоторого множества рёбер  графа (), то элемент  будет на­
ходиться  уровнями ниже  в решётке   (, ), где  = ||. Таким
образом, для доказательства хроматической определяемости некото­
рого полного многодольного графа достаточно показать, что он хро­
матически не эквивалентен ни одному графу, находящемуся с ним на
одном уровне в решётке   (, ), и что, удаляя ребра из элемен­
тов меньшего уровня в решётке, нельзя получить граф, хроматически
эквивалентный данному. Хроматическую неэквивалентность графов
мы часто показываем, сравнивая значения инвариантов (,  + 1)
соответствующих графов. Для этого нами получена оценка измене­
ния этого инварианта при удалении рёбер из графа, а именно,  ≤
(,  + 1) − (,  + 1) ≤ 2 − 1. Отметим, что наибольшую слож­
ность при доказательствах вызывает случай  = 2. Причина этой
сложности заключается в том, что при малых значениях некоторых
из чисел 1 , 2 , . . . ,  разность (,  + 1) − (,  + 1) вычисляется
довольно сложным образом. В первом параграфе второй главы нами
фактически указан метод вычисления данной разности, что откры­
вает, по нашему мнению, хорошую перспективу для подтверждения
сформулированной гипотезы в общем виде.
Во втором и третьем параграфах второй главы доказывается
хроматическая определяемость полных многодольных графов, имею­
щих в решётке   (, ) высоту 2 и 3, соответственно. Результатом
15
этой главы является следующая Теорема 2, которая является вторым
основным результатом диссертации.
Пусть  и  — натуральные числа такие, что  < .
Тогда любой полный -дольный -граф с неодноэлементными долями,
имеющий высоту ≤ 3 в решётке   (, ), является хроматически
определяемым.
Теорема 2.
Если соотнести результаты, полученные нами, с результатами пред­
шествующих исследований, то получим следующее.
В работах [10], [15] и [16] рассмотрен элемент 12 , элемент 5 при
условии  =  − 1 и элемент 19 при условии  =  − 2.
Что касается результата Цао, Ли, Лью и Йе [18], в случае элемен­
тов высоты 2 и 3 мы улучшили оценку  ≥  2 /4 + 1 до оптимальной
оценки  ≥ 2.
Автор выражает глубокую признательность своему научному ру­
ководителю профессору Виталию Анатольевичу Баранскому за поста­
новки задач и постоянное внимание к работе.
Список литературы
[1]
Birkhoff, G.D.
[2]
Whitney, H. The coloring of graphs // Annal. Math. 1932. Vol. 33.
[3]
Read, R.C. An introduction to chromatic polynomials // J. Comb.
[4]
Chao, C.Y., Whitehead Jr., E.G.
[5]
Read, R.C., Tutte, W.T.
[6]
Koh, K.M., Teo, K.L. The search for chromatically unique graphs
[7]
Chia, G.L.
A determinant formula for the number of ways of
coloring a map // Annal. Math. 2nd Ser. 1912–1913. Vol. 14. P. 42–46.
P. 688–718.
Theory. 1968. Vol. 4. P. 52–71.
On chromatic equivalence of
graphs // Theory and Appl. of Graphs. 1978. Vol. 642. P. 121–131.
Chromatic polynomials // Selected
Topics in Graph Theory III. Academic Press. 1988. P. 15–42.
II // Discrete Math. 1997. Vol. 172. P. 59–78.
Some problems on chromatic polynomials // Discrete
Math. 1997. Vol. 172. P. 39–44.
16
[8]
[9]
Liu, R.Y. Adjoint polynomials and chromatically unique graphs //
Discrete Math. 1997. Vol. 172. P. 85–92.
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:
[11]
Li, N.Z., Liu, R.Y.
[12]
Koh, K.M., Teo, K.L. The search for chromatically unique graphs
[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.
[15]
Xu, L.M. Chromatic uniqueness of complete -partite graphs ( −
W¨
ohrmann Print Service, 2005. 169 p.
The chromaticity of the complete –partite
graph (1; 2 ; ..;  ) // Xinjiang Univ. Natur. Sci. 1990. Vol. 7, № 3.
P. 95–96.
// Graphs Combin. 1990. Vol. 6. P. 259–285.
A note on chromatic uniqueness of
completely tripartite graphs // J. Math. Res. Exposition 2010. Vol. 30,
№ 2. P. 233–240.
, , ..., ) (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
[17]
Chao, C.Y., Novacky Jr., G.A. On maximally saturated graphs
[18]
Zhao, H.X., Li, X.L., Liu, R.Y., Ye, C.F. The chromaticity of
[19]
Баранский, В.А., Королева, Т.А.
-partite graphs // Ars Combin. 2009. Vol. 92. P. 353–376.
// Discrete Math. 1982. Vol. 41. P. 139–143.
certain complete multipartite graphs // Graphs and Combin. 2004.
Vol. 20. P. 423–434.
Решетка разбиений нату­
рального числа // Доклады Академии Наук. 2008. Том 418, № 4.
С. 439–442.
17
Баранский, В.А., Королева, Т.А.
[20]
Хроматическая определя­
емость атомов в решетках полных многодольных графов // Тр.
Ин-та математики и механики УрО РАН. 2007. Т. 13, № 3. С. 22–29.
[21]
Королева, Т.А. Хроматическая определяемость некоторых пол­
[22]
Королева, Т.А. Хроматическая определяемость некоторых пол­
[23]
Баранский, В.А., Королева, Т.А. Хроматическая определяе­
[24]
Асанов, М.О., Баранский, В.А., Расин, В.В.
[25]
Farrell, E.J.
[26]
Зыков, А.А. Основы теории графов. М.: “Вузовская книга”, 2004.
ных трехдольных графов. I // Тр. Ин-та математики и механики
УрО РАН. 2007. Т. 13, № 3. С. 65–83.
ных трехдольных графов. II // Изв. Урал. гос. ун-та. 2010. № 74.
С. 39–56.
мость некоторых полных трехдольных графов // Изв. Урал. гос.
ун-та. 2010. № 74. С. 5–26.
Дискретная
математика: графы, матроиды, алгоритмы. СПб.: “Лань”, 2010.
368 с.
On chromatic coefficients // Discrete Math. 1980.
Vol. 29. P. 257–264.
664 с.
Работы автора по теме диссертации
[27]
Сеньчонок, Т.А., Баранский, В.А.
[28]
Сеньчонок, Т.А. Хроматическая определяемость элементов вы­
[29]
Баранский, В.А., Сеньчонок, Т.А. Хроматическая определя­
Классификация элемен­
тов малой высоты в решетках полных многодольных графов //
Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 2.
С. 159–173.
соты 2 в решетках полных многодольных графов // Тр. Ин-та
математики и механики УрО РАН. 2011. Т. 17, № 3. С. 271–281.
емость элементов высоты ≤3 в решетках полных многодольных
графов // Тр. Ин-та математики и механики УрО РАН. 2011.
Т. 17, № 4. С. 3–18.
18
[30]
Сеньчонок, Т.А.
[31]
Баранский, В.А., Сеньчонок, Т.А. О хроматической опреде­
[32]
Баранский, В.А., Сеньчонок, Т.А. Хроматическая определя­
[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]
Сеньчонок, Т.А.
О хроматической определяемости элементов
высоты 2 в решётках полных многодольных графов // Тезисы 42-й
Всероссийской молодежной школы-конференции. Екатеринбург:
Институт математики и механики УрО РАН. 2011. С. 241–243.
ляемости элементов малой высоты в решетках полных многодоль­
ных графов // XIV Всероссийская конференция Математическое
программирование и приложения (тезисы докладов). Екатерин­
бург: УрО РАН. 2011. С. 150–151.
емость элементов высоты ≤3 в решетках полных многодольных
графов // Тезисы Международной конференции по алгебре и гео­
метрии, посвящённой 80-летию со дня рождения А.И.Старостина.
Екатеринбург: Изд-во “УМЦ-УПИ”. 2011. С. 16–17.
О свойствах хроматического инварианта
(,  + 1) // Тезисы Международной (43-й Всероссийской) мо­
лодежной школы-конференции. Екатеринбург: Институт матема­
тики и механики УрО РАН. 2012. С. 84–86.
19
Документ
Категория
Физико-математические науки
Просмотров
41
Размер файла
387 Кб
Теги
кандидатская
1/--страниц
Пожаловаться на содержимое документа