Введение к работе
Актуальность темы
Изучение раскрасок графов началось с задачи о четырёх красках. Более чем столетняя история попыток решения этой задачи сыграла положительную роль в развитии различных разделов теории графов и особенно для исследования свойств раскрасок графов. Во многих работах было показано важное прикладное значение раскрасок графов для задач теории расписаний, задач распараллеливания численных методов, задач экономии памяти, задач распределения ресурсов, технологий цифровых водяных знаков и многих других задач.
Для нас важно отметить, что в 1912 году попытки решить проблему четырёх красок привели Биркгофа [1] к понятию хроматического многочлена карты. Это понятие в 1932 году было обобщено Уитни [2] на произвольный граф. Им же было найдено несколько фундаментальных свойств хроматических многочленов графов. В 1968 году Рид [3] ввёл понятие хроматически эквивалентных графов, т. е. графов, имеющих одинаковые хроматические многочлены, и сформулировал задачу о необходимых и достаточных условиях хроматической эквивалентности графов. В 1978 году Чао и Уайтхед [4] ввели понятие хроматически определяемого графа, т. е. графа, который определяется своим хроматическим многочленом с точностью до изоморфизма. Они же нашли некоторые семейства хроматически определяемых графов. Хотя Биркгоф и не смог решить проблему четырёх красок с помощью хроматических многочленов, его исследования породили в теории раскрасок графов множество работ других авторов по хроматической эквивалентности и хроматической определяемости графов. Данное направление активно развивается и в настоящее время. Состояние дел в этой области достаточно полно изложено в обзорных статьях [5-8] и монографиях [9, 10].
Особое место в исследовании хроматической определяемости графов занимает изучение полных многодольных графов, так как любая раскраска графа — это вложение этого графа в некоторый полный многодольный граф. То есть любой граф, раскрашиваемый st цветов, можно получить из полного /-дольного графа удалением некоторого множества рёбер. Поэтому, опираясь на хроматические свойства полных многодольных графов, можно исследовать хроматическую опре-деляемость любых других классов графов. Полные t-дольные графы будем обозначать через K(ni,ri2,...,щ), где пі,П2, ,Щ — размеры
всех t долей этого графа. Рассматривая полные t-дольные графы будем всегда предполагать, что п\ > щ > ... > Щ.
В 1990 году Ли и Лью [11] доказали, что граф K(ni,..., п^_і, 1) является хроматически определяемым тогда и только тогда, когда 2 > П\ > ... > щ~\ > 1. В силу этого в дальнейшем нас будет интересовать хроматическая определяемость полных многодольных графов только с неодноэлементными долями.
Задача о хроматической определяемости полных многодольных графов привлекала внимание значительного числа исследователей, при этом особым интересом пользовались случаи двух- и трёхдольных графов. Хроматической определяемости двудольных гафов было посвящено множество работ, и, наконец, в 1990 году Кох и Тео [12] доказали, что любой полный двудольный граф хроматически определяем, если его доли неодноэлементны. После этого задачи для двудольных графов фокусируются вокруг удаления из них определённых наборов рёбер и доказательства хроматической определяемости получившихся графов (см., например, [13]). Что же касается полных трёхдольных графов, то их хроматическая определяемость до сих пор не доказана в общем случае, т. е. когда доли графа неодноэлементны. В настоящее время продолжается исследование хроматической определяемости некоторых классов полных трёхдольных графов (см., например, [14]).
Многие же исследования направлены на произвольные полные t-дольные графы. В них можно выделить два основных направления исследований. Часть исследований, по аналогии с трёхдольными графами, касается доказательства хроматической определяемости полных t-дольных графов определённого вида. Доказано, что хроматически определяемы следующие многодольные графы.
-
К(р,р,... ,р,р - к) при к > 2, t > 4 и р > к + 2 (Цао, 2005 [10]).
-
К(р,р,... ,р,р — 1,р — к) при к > 2, і > 4 и|) > fc + 2 (Ксю, 2008 [15]).
-
К(р,...,р,р — 1,...,р — 1,р — к) при р>; + 2>4и><і + 3>3
t-d-2 d+l
(Лау и Пенг, 2009 [16]).
В этих случаях авторы брали классы полных трёхдольных графов, хроматическая определяемость которых уже была доказана, и
обобщали полученные результаты на произвольное число долей в графе. Заметим, что хроматическая определяемость этих полных многодольных графов доказана в общем виде, т. е. в случае, когда доли графа неодноэлементны.
Другая часть исследований обращена к обобщению утверждения Чао и Новацки [17], которые в 1982 году доказали, что для любого t > 2 полный t-дольный граф K(ni,ri2, ,щ) хроматически определяем, если \пі — rij\ < 1 для всех г, j = 1, 2,..., t. В этом направлении следует отметить результат Цао [10], он доказал, что если \п{ — rij\ < 2 и п\ > ri'i > ... > щ > t + 1, то K(ni}ri2}... }щ) хроматически определяем при t > 2. Если обобщить задачу для произвольного значения \п{ — rij\ < к (г,j = 1,2,...,^), то ответ на этот вопрос дали Цао, Ли, Лью и Ие [18], они показали, что если \щ — rij\ < к и п\ > fi'i > ... > щ > tk2/4: + 1 для некоторого натурального числа к, то К{п\,П2, ,щ) хроматически определяем. В этих исследованиях доказана хроматическая определяемость полных многодольных графов с серьёзным ограничением на размеры долей этих графов (/ достаточно велико).
Учитывая исследования различных авторов можно сформулировать следующую гипотезу: любой полный многодольный граф
К{гі\, ЇІ2, і Щ) ЯВЛЯеТСЯ ХрОМаТИЧеСКИ Определяемым При П\ > ГІ2 >
... >щ > 2.
Графы, хроматическую определяемость которых мы будем исследовать, характеризуются своим положением в некоторой решётке полных /-дольных графов. Использовать решёточный порядок для доказательства хроматической определяемости полных многодольных графов предложили Баранский и Королёва [19] в 2007 году. Хроматическая определяемость наименьшего элемента этих решёток была доказана Чао и Новацки [17]. В работе [20] установлена хроматическая определяемость атомов этих решёток при щ > 2. Элементы высоты 2 и 3 этих решёток при t = 3 рассмотрены в работах [21-23], там же доказана хроматическая определяемость полных трёхдольных графов, имеющих высоту 2 и 3 в решётках полных трёхдольных графов.
Цели работы состоят в следующем:
-
Дать классификацию элементов высоты < 3 в решётках полных t-дольных графов при t > 4.
-
Доказать хроматическую определяемость полных многодольных
графов с неодноэлементными долями, имеющих высоту < 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 наименования.
