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

• Автор: Сеньчонок, Татьяна Александровна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Екатеринбург
• Количество страниц: 125 с. : ил.

Содержание
Введение
Глава 1. Описание элементов высоты < 3 в решётках NPL(n,t)
1.1. Решётки NPL(n,t) и хроматические инварианты
1.2. Классификация элементов высоты 2 и 3 в решётках NPL(n,t)
1.3. Нижние этажи решёток NPL(n,t)
Глава 2. Хроматическая определяемость элементов высоты < 3 в решётках NPL(n,t)
2.1. Раскраски графов и свойства хроматических инвариантов
2.2. Хроматическая определяемость элементов высоты 2 в решётках NPL(n,t)
2.3. Хроматическая определяемость элементов высоты 3 в решётках NPL(n,t)
Литература

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

же касается исследований, связанных с хроматическими многочленами, то они стали весьма разнообразными и обширными. Состояние дел в этой области достаточно полно изложено в обзорных статьях [18-22] и монографиях [23, 24].
Перейдём теперь к точному определению используемых нами понятий, к формулировке цели исследования и описанию работ предшественников.
В данной работе мы рассматриваем только обыкновенные графы, т. е. графы без петель и кратных рёбер. Обозначения и терминологию для графов будем использовать в соответствии с [25].
Пусть С — произвольный (п, то, Афграф, т. е. граф, имеющий п вершин, то рёбер и к компонент связности. Раскраской или Ь-раскраской графа (9 называется отображение ф из множества вершин V графа (9 в множество натуральных чисел {1, 2
Для натурального числа х через Р((9, х) обозначим число всевозможных раскрасок графа Є в х заданных цветов, причём не предполагается, что в раскраске должны быть использованы все х цветов. Хорошо известно, (см., например, [3] или [25]), что функция Р((9, х) является многочленом степени п от х, который называют хроматическим многочленом графа (9. Два графа называются хроматически эквивалентными или Х'эквивалентпыми1 если они имеют одинаковые хроматические многочлены.
Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвари-

7. Найдём теперь покрытия элемента
Ь7 = (д + 3,д+ 1,.„,д+ 1,д,„-,д),
г—3 <—г+2
который при условии 3 = г < £ — 1 совпадает с с — (д+3, д

элементом высоты 2, а при условии 4 < г < £ ~- 1 имеет высоту 3.
7.1. Подъём и косдвиг блока из (д+3)-кластера невозможен, так как этот кластер является первым и одноэлементным.
7.2. Подъём блока из (д + 1)-кластера возможен при условии г — 3 = 1,
поэтому при условии 4 = г < £ — 1 мы получаем элемент высоты
сб = ($ + 4,) = (д + + 1
t—r+, г—4 1—г+3
7.3. Косдвиг блока в (д + 1)-кластере возможен при условии г — 3 > 2,
поэтому при условии 5 < г < £ — 1 мы получаем элемент высоты
13 = (я + 3, д + 2, + 1,. „ , д + 1, г—5 £—г+3
7.4. Рассмотрим подъём блока из д-кластера.
7.4.1. Пусть подъём блока происходит в (д + 3)-кластер. Тогда г — 3 = О и £ — г + 2 = 1, т. е. £ = 2, что невозможно.
7.4.2. Пусть подъём блока происходит в (д + 1)-кластер. Тогда г — 3=1 и £ — г + 2 = 1, т. е. £ = 3, что невозможно.
7.5. Косдвиг блока в д-кластере возможен при условии £ — г + 2 > 2, поэтому при условии 3 = г < £ — 1 мы получаем элемент высоты 3, а при условии 4 < г < £ — 1 — элемент высоты