О хроматической определяемости некоторых классов трехдольных графов, хроматических инвариантах и решётках разбиений натуральных чисел тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Гейн Павел Александрович

• Гейн Павел Александрович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Гейн Павел Александрович

2.4 Общий случай

2.5 Улучшенная оценка инварианта рЪ, если (Е) содержит треугольник

2.6 Оценка инварианта рЪ, если (Е) содержит ^-подграф

2.7 Оценка инварианта рЬ, если Е содержит малое число элементов

Глава 3. Хроматическая определяемость графов К(з,8 — 1, й — к)

Глава 4. Хроматическая определяемость некоторых полных трехдольных графов

4.1 Введение

4.2 Случай г =

4.3 Случай г =

4.4 Случай г =

Публикации автора по теме диссертации

Заключение

ВВЕДЕНИЕ

Теория раскрасок графов ведет свое начало с задачи о четырех красках. В 1852 году Френсис Гутри заметил, что достаточно четырех цветов чтобы раскрасить карту графств Англии, и задался вопросом, верно ли что для раскраски любой карты достаточно лишь четырех цветов. На протяжении многих лет многие математики трудились над разрешением этой проблемы. В 1879 году Кемпе предложил доказательство, однако, в 1890 году Хивуд обнаружил в нем ошибку. Хивуд, основываясь на методе доказательства Кемпе, показал, что для раскраски любой карты достаточно пяти цветов.

При исследовании гипотезы о четырех красках Биркгоф в 1912 году ввел понятие хроматического многочлена карты [1]. В 1932 году Уитни [2] обобщил это понятие на случай произвольного графа и установил несколько свойств таких многочленов. В монографии [3] можно найти множество свойств хроматических многочленов.

В 1968 году Рид [4] ввел понятие хроматически эквивалентных графов. Два графа называются хроматически эквивалентными, если их хроматические многочлены совпадают.

Введение диссертации (часть автореферата) на тему «О хроматической определяемости некоторых классов трехдольных графов, хроматических инвариантах и решётках разбиений натуральных чисел»

Актуальность темы

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

Пусть С = (V., Е) — граф с множеством вершин V и множеством ребер Е. Также мы будем обозначать множество вершин графа С через V(С), а множество ребер — через Е(С). Если Н — подграф С, то мы будем писать Н ^ С.

Раскраской графа С в Ь цветов (или 1-раскраской) называется такое отображение р: V ^ {1, 2,... ,1}, что у(и) = р(у) для любых двух смежных вершин и и V графа С. Числа 1, 2,... будем называть цветами. Граф называется Ь-раскрашиваемым, если существует его раскраска в Ь цветов. Минимальное £, для которого существует раскраска графа С в Ь цветов называется хроматическим

числом графа G и обозначается через

Число раскрасок графа G в х цветов обозначим через Р(G,x). Хорошо известно (см., например, [6]), что функция Р(G,x) есть многочлен от переменной х, который называется хроматическим многочленом графа G. Некоторые свойства хроматических многочленов могут быть найдены в [6], здесь мы отметим, что степень хроматического многочлена равна числу вершин в графе.

Задача вычисления коэффициентов хроматического многочлена достаточно сложна. Пусть Р(G,x) = ^'=0 biX1. Уитни [5] доказал, что

\Е\

= Е(-!)Г N (г,г),

г=o

где N(i,r) — число остовных подграфов графа G, содержащих i компонент связности и г ребер.

В этой же работе Уитни показал, что число слагаемых в сумме может существенно сокращено. Он доказал следующее утверждение, известное как теорема о разрушенных циклах. Зафиксируем произвольное биективное отображение ß: Е ^ 1, 2,..., \ Е |. Для произвольного цикла С обозначим через е такое ребро этого цикла, что для любого ребра е' £ С \ {е} выполняется ß(е') < ß(е). Множество С \ {е} назовем разрушенным циклом относительно ß. Тогда

Ъг = (-1)\у\-%(G),

где hi — число остовных подграфов, содержащих \ V\ — i ребер и не содержащих разрушенных циклов относительно ß.

Другой способ вычисления хроматического многочлена предложил Матия-севич в [7]. Зафиксируем произвольную ориентацию ребер, и для произвольного ребра е £ Е через ё и е" обозначим начало и конец ребра е соответственно. Обозначим через Z кольцо вычетов по модулю к. Потоком по модулю к назовем произвольную функцию из Е в Z. Поток s назовем сбалансированным, если он не имеет истоков-стоков, т. е. если для любой вершины v выполняется

Y, »V ) = Е'У

е'=v e"=v

Отметим, что суммирование происходит в кольце Z^. Поток s назовем невырожденным, если для любого ребра е £ Е выполняется s(e) = 0. Для графа

С число невырожденных сбалансированных потоков обозначим через Р (С, к). Матиясевич доказал, что

Р(Г г) = (х -1)|Е| V р{На) г I ^ ^ клщн)1.

н

Еще один способ вычисления хроматического многочлена предложил Зыков в [8]. Рассмотрим произвольную ¿-раскраску графа С. Заметим, что любые две одноцветные вершины несмежны, следовательно, каждый одноцветный класс образует коклику, т. е. множество вершин, порождающее нулевой подграф. Таким образом, любая раскраска порождает разбиение множества вершин графа на коклики. Обозначим через рЬ(С, г) число разбиений множества вершин графа С на г непустых коклик. Зыков доказал, что хроматический многочлен графа С можно представить в виде

п

Р(С,х) = ^рЬ(С, г)х(1\

где через х(г) обозначена факториальная степень переменной х, т. е. х(г) = х(х — 1) • ... • (х — % + 1).

Два графа называются хроматически эквивалентными, если они имеют одинаковые хроматические многочлены. Класс эквивалентности по этому отношению называется хроматическим классом графа. Известно, (см. например, [6]), что для любого натурального п все деревья на п вершинах образуют хроматический класс.

Граф называется хроматически определяемым, если он изоморфен любому своему хроматически эквивалентному графу. Это понятие ввели Чао и Уатхед в 1976 г. в работе [9]. Они же установили хроматическую определяемость графов из некоторых семейств [10, 11, 12].

Предположим, что каждому графу приписано некоторое число а. Это число называется хроматическим инвариантом, если оно одинаково для всех хроматически эквивалентных графов. Хорошо известно(см. [6, 13, 14]), что хроматическими инвариантами являются число вершин, число ребер и число треугольников, содержащихся в графе С. Число ребер графа С будем обозначать через 12(0), а число треугольников — через 13(С).

Для хроматического инварианта а и произвольных графов G\ и G2 введем обозначение

Aa(Gi,G2) = a(Gi) - a(G2).

Поскольку по теореме Зыкова [8] хроматический многочлен графа G можно представить в виде

п

р (G,x) = ^ pt(G,i)x(t),

i=x

числа pt(G, i) являются хроматическими инвариантами. В дальнейшем нас особенно будет интересовать инвариант pt(G, х +1), который мы будем обозначать просто через pt.

Граф называется t-уникально раскрашиваемым, если он ¿-раскрашиваем и любая его раскраска в t цветов порождает одно и то же разбиение множества вершин на одноцветные классы. Другими словами, граф G является t-уникально раскрашиваемым, если pt(G,t) = 1.

Граф G называется t-дольным графом, если множество его вершин можно разбить на t непустых коклик (долей), таким образом что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой доли; если каждая вершина соединена с каждой вершиной из других долей, то такой граф называют полным t-дольным графом и обозначают через К[п\,п2,... ,щ), где п\,п2,.. .щ есть последовательность чисел вершин в долях этого графа. Мы будем всегда предполагать, что размеры долей записаны в неубывающем порядке, т. е. п\ ^ п2 ^ ... ^ nt.

Ясно, что хроматическое число любого полного ¿-дольного графа равно t и любой полный ¿-дольный граф является ¿-уникально раскрашиваемым. Из этого следует, что если некоторый граф H хроматически эквивалентен полному ¿-дольному графу, то H есть ¿-уникально раскрашиваемый граф.

Заметим, что задать раскраску графа в ¿-цветов эквивалентно тому, что задать изоморфное вложение графа в некоторый полный ¿-дольный граф, построенный на этом же множестве вершин. В частности, это означает, что любой ¿-раскрашиваемый граф может быть получен из некоторого полного ¿-дольного графа с помощью удаления некоторого множества ребер. Этим определяется важная роль, которую играют полные многодольные графы в теории раскрасок графов. Полные ¿-дольные графы — это максимальные ¿-раскрашиваемые

графы.

Все полные графы Кп являются хроматически определяемыми, поскольку они и только они имеют хроматический многочлен х(п\ Возникает естественный вопрос: сохраняется ли свойство хроматической определяемости при удалении ребер из полного графа?

Лоренц и Уайтхед в 1981 году [15] изучали графы, полученные удалением из полного графа множества из к (0 < 2к ^ п) независимых ребер, то есть паросо-четаний из к ребер. Они показали, что все такие графы являются хроматически определяемыми. Заметим, что каждый такой граф изоморфен некоторому полному многодольному графу К(п\,п2,... ,щ), где Ь ^ 2 и 1 ^ щ ^ 2 для всех г = 1, 2,... ,£. Этот результат был обобщен Чао и Новацким в 1982 году [16]. Они доказали, что полный многодольный граф К(п\,п2,... ,щ) является хроматически определяемым при £ ^ 2 и

\пг — щI < 1

для всех г,] = 1, 2,... £.

В силу важности полных многодольных графов, большое число исследований различных авторов было посвящено хроматической определяемости полных многодольных графов. Достаточно полный обзор исследований в области полных многодольных графов может быть найден в монографиях [3] и [33].

Хроматической определяемости полных двудольных графов были посвящены работы [17, 18]. В 1990 году Кох и Тео в работе [19] и независимо от них в 1994 году Донг в работе [20] доказали, что полный двудольный граф К(п1,п2) хроматически определяем при п\ ^ п2 ^ 2.

После этого внимание исследователей в случае двудольных графов было сосредоточено на графах, получаемых из полных двудольных графов удалением некоторого числа ребер, и доказательства их хроматической определяемо-сти [21, 22, 23, 24].

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

1. Граф К(п — к,п,п) при п ^ к + у, см. [25].

2. Граф К(п, п,п + к) при п ^ , см. [26].

3. Граф К(п — к,п,п + к) при п ^ к2 + ^к, см. [27].

4. Граф К(п — 4, п, п) при п ^ 6, см. [28].

5. Граф К(п\,п1,п3) является хроматически определяемым, если щ > п3 ^ 2, см. [30, 31].

6. Граф К(п\, п\ — 1, п3) является хроматически определяемым, если п3 ^ 2 и 2п3 ^ п\, см. [30].

7. Граф К(п\,п2,п3) при п\ ^ п2 ^ п3 ^ 2 и п\ — п3 ^ 4, см. [35, 36, 37].

Другая часть исследований посвящена обобщению результата Чао и Новац-ки [16]. В связи с этим Кох и Тео поставили следующую задачу: будет ли граф К(п\,п2,... ,nt) хроматически определяем, если

|П» — Uj | ^ 2

для всех i,j = 1, 2,... ,t и число nt достаточно велико, где щ ^ п2 ^ ... ^ nt? В 1985 году Гьюдичи и Лопее [32] доказали, что полные ¿-дольные графы

К(q + 1,q,... ,q,q — 1)

хроматически определяемы при t ^ 2 и q ^ 3. Более общий ответ на поставленный вопрос получил Цао [33], он доказал, что если

|ni — nj | ^ 2 и п\ ^ п2 ^ ... ^ nt ^ t + 1,

то К(п\,п2,... ,щ) хроматически определяем при t ^ 2.

Если обобщить задачу для произвольного значения — nj| ^ к (i,j = 1, 2,... ,t), то ответ на этот вопрос дали Цао, Ли, Лью и Йе [34], они показали, что если

|п» — rij | ^ к и П\ ^ п2 ^ ... ^ nt ^ tk2/4 + 1

для некоторого натурального числа к, то К(п\,п2,... ,nt) хроматически определяем.

Отметим, что наибольшую трудность для доказательства хроматической определяемости К(п\,п2,... ,nt) составляют случаи, когда nt мало, и в особенности случаи, когда nt = 2.

В работах [38, 39] Баранским и Сеньчонок было доказано, что полный многодольный граф К(п\,п2,п3,.. .щ) является хроматически определяемым, если г ^ 4 и

— Щ ^ 4 и п\ ^ п2 ^ ... ^ щ ^ 2.

В 1990 году Ли и Лью [40] доказали, что граф К(п\,п2,... , 1) является хроматически определяемым только и только тогда, когда

2 ^ щ ^ ... ^ пг ^ 1.

Отметим, что этот результат вместе с результатом Коха и Тео [19] решают задачу о хроматической определяемости полных двудольных графов: полный двудольный граф К(п\, п2) является хроматически определяемым тогда и только тогда, когда его наименьшая доля содержит не менее двух вершин.

В ходе исследований различных авторов возникла следующая гипотеза:

Любой полный многодольный граф К(п\,п2,... ,щ) является хроматически определяемым при п\ ^ п2 ^ ... ^ щ ^ 2.

Цель работы

Данная работа преследует две следующие цели

(a) исследование хроматических инвариантов;

(b) исследование хроматической определяемости полных трехдольных графов.

Основные результаты

1. Получена новая оценка инварианта на классе уникально раскрашиваемых графов.

2. Доказана хроматическая определяемость полных трехдольных графов

К(п\,п2,п3),п\ ^ п2 ^ п3 ^ 2 при выполнение одного из следующих условий:

П2 = П\ — 1

или

Щ — п3 ^ 5. 9

Научная новизна

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

Методы исследований

При исследовании хроматический инвариантов и хроматической определя-емости использовались методы комбинаторного анализа, алгебры и теории чисел.

На защиту выносится

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

Апробация работы

Основные результаты докладывались на следующих конференциях: 47 и 49 Международной молодежной школе-конференции «Современные проблемы математики и ее приложений» SOPROMAT (Екатеринбург, 2016 и 2018), Международной конференции и школе для аспирантов и магистрантов «G2M2: Группы и графы, метрики и многообразия» (Екатеринбург, 2017), Конференции международных математических центров мирового уровня (Сочи, 2021). Так же результаты докладывались на семинаре "Алгебраические системы" (УрФУ, рук. Л.Н. Шеврин).

Публикации

Основные результаты по теме диссертации изложены в 4 статьях. Все публикации индексируются в базах данных Web of Science и/или Scopus.

Личный вклад

Личный вклад состоит в непосредственном получении всех результатов и подготовке публикаций по теме диссертации.

Структура и объем работы

Диссертация изложена на 94 страницах, содержит введение, четыре главы, заключение, список публикаций автора по теме диссертации и список литературы, состоящий из 52 источников.

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

В первой главе описываются решетки разбиений натуральных чисел и устанавливаются основные свойства хроматических инвариантов. Эти объекты

дают основной инструментарий для доказательства хроматической определяе-мости полных многодольных графов.

Кратко опишем здесь решетки разбиений натуральных чисел, более подробное изложение можно найти в статьях [43, 44].

Разбиением натурального числа п называется последовательность целых неотрицательных чисел и = (и1,и2,...) такая, что и1 ^ и2 ^ ..., последовательность и содержит лишь конечное число ненулевых членов и п = ^^ 1 щ. Длиной разбиения и называется такое число I, что щ > 0 и и1+1 = и1+2 = ... = 0. При записи разбиений мы будем часто опускать их нулевые члены.

Основы теории разбиений были заложены Леонардо Эйлером XVIII веке. В монографиях [41, 42] приведены сведения по этой теории.

На множестве всех разбиений натурального числа п введем отношение порядка следующим образом. Пусть и = (и1,и2,...) и V = (у1,у2, ...) — два разбиения числа п. Тогда V < и, если

у1 ^ и1,

VI + У2 < Щ + 42,

V1 + У2 + ... + V— < Щ + Щ + ... + Щ—1,

где £ - наибольшая из длин разбиений и и V. Отношение < называют отношением доминирования. В работе [43] показано, что все разбиения числа п образуют решетку относительно <1.

В работе [44] отмечено, что все разбиения фиксированной длины числа п образуют решетку относительно <. Решетку всех разбиений длины £ натурального числа п будем обозначать через ЫРЬ(п,Ь). Нас особенно будут интересовать решетки ЫРЬ(п, 3).

Рассмотрим произвольный полный многодольный граф К(и1,и2,... ,щ), где Щ ^ и2 ^ ... ^ щ, и обозначим п = и1 + и2 + ... + щ. Отметим, что последовательность и = (и1,и2,... ,щ, 0,0,0,...) есть разбиение числа п. Таким образом, установлено взаимно-однозначное соответствие между всеми полными ¿-дольными графами на п вершинах и разбиениями длины £ числа п. В дальнейшем, для краткости мы будем обозначить К (и1,и2,... ,щ) через К (и), где и = (и1,и2,... ,щ).

Установленное выше взаимно-однозначное соответствие позволяет отождествить полные трехдольные графы на п-вершинах и разбиения длины 3 числа п. Следовательно, можно рассмотреть отношение < на множестве всех трехдольных графов. В главе 1 описана взаимосвязь между хроматическими инвариантами и этим отношением порядка. Особое внимание в этой главе уделено числу ребер (12) и числу треугольников (13).

Во второй главе исследуется хроматический инвариант рЪ. Отметим, что этот инвариант также используется при исследовании хроматической опреде-ляемости двудольных графов, см., например, [45].

Пусть а(С) - некоторый хроматический инвариант, С\ и С2 — произвольные графы. Введем обозначение: Аа(С\,С2) = а(С\) — а(С2).

Пусть Н — произвольный ¿-уникально раскрашиваемый граф Н. Предположим, что граф Н получен удалением множества ребер Е из полного многодольного графа К (у) = К (у\,у2,у3, ... ,Уг). В работе [46] была получена оценка

\Е\ < Ар£(Н,К(у)) < 21е\ — 1,

которая играла важную роль при доказательствах хроматической определяе-мости некоторых полных многодольных графов.

Основной целью главы 2 является улучшение этой оценки. В работе [39] был представлен комбинаторный способ вычисления значения АрЪ(Н,К(у)) в случае ¿-уникально раскрашиваемого графа Н. Усовершенствовав метод, предложенный в [39], мы улучшили данную оценку.

Долю графа К (у) назовем активной, если одна из вершин некоторого ребра из Е лежит в этой доле. Подграф Н', изоморфный графу К (в, 1), где й > 1, назовем согласованным, если все й вершин первой доли графа К (в, 1) лежат в одной и той же доле графа К (у). Граф, ребернопорожденный множеством Е, будем обозначать через (Е).

Основным результатом второй главы является следующая

Теорема 1. Пусть каждая активная доля графа К(у\,у2, ... ,Уг) содержит не менее трех вершин, граф Н получен удалением множества ребер Е из графа К(у\,у2, ... ,Уг) и Н есть Ь-уникально раскрашиваемый граф. Тогда

1) если Е порождает согласованный подграф К(\Е\, 1), то

Арг(Н,К (у)) = 2\е \ — 1;

2) если (Е) содержит треугольник, то

Ар1(Н, К (у)) ^ 2\е\—2 + ^^ — 3\Е \ + 13,

3) иначе

АрЪ(Н,К(V)) < 2^—1 + 1. Теорема 1 применяется нами в главах 3 и 4.

Третья и четвертая главы посвящены хроматической определяемости полных трехдольных графов. Основным результатом третьей главы является следующая

Теорема 2. Граф К(з,8 — 1, з — к) является хроматически определяемым при к ^ 1 и в — к ^ 2.

Эта теорема улучшает результат из работы [30], в которой данное утверждение было доказано при условии в ^ 2к.

Четвертая глава посвящена обобщению результатов Чао и Новацки [16], а также Баранского и Королевой [35, 36, 37]. Доказательство основывается на усовершенствовании метода, предложенного в работах [35, 36, 37].

Из результата Чао и Новацки в [16] следует хроматическая определяемость наименьших элементов в решетках ЫРЬ(п, 3). В работе [35] была показана хроматическая определяемость атомов в этих решетках, в работах [36, 37] была показана хроматическая определяемость графов высоты не более трех в этих решетках. В работах [38, 39] этот результат был обобщен на случай полных многодольных графов, имеющих более трех долей.

Основным результатом четвертой главы является следующая

Теорема 3. Пусть п — натуральное число. Тогда любой полный трехдольный п-граф с неодноэлементными долями, имеющий высоту не более четырех в решетке ЫРЬ(п, 3), является хроматически определяемым.

Эта теорема допускает следующую эквивалентную формулировку.

Теорема 3'. Граф К(п\,п2,п3) является хроматически определяемым, если Щ ^ п2 ^ п3 ^ 2 и щ — п3 ^ 5.

Данная теорема улучшает результат работ [35, 36, 37].

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

ГЛАВА 1

РЕШЕТКА РАЗБИЕНИЙ НАТУРАЛЬНЫХ ЧИСЕЛ И ХРОМАТИЧЕСКИЕ ИНВАРИАНТЫ

Разбиением натурального числа п называется невозрастающая последовательность целых неотрицательных чисел и = (и1,и2,...) такая, что и1 ^ и2 ^ ..., последовательность и содержит лишь конечное число ненулевых членов и п = ^1 щ. Длиной разбиения и называется такое число I, что щ > 0 и и1+1 = щ+2 = ... = 0. При записи разбиений мы будем часто опускать их нулевые члены.

На множестве всех разбиений натурального числа п введем отношение порядка следующим образом. Пусть и = (и1,и2,...) и V = (у1,у2, ...) — два разбиения числа п. Тогда V < и, если

у1 ^ и1, V1 + У2 < Щ + 42,

V1 + У2 + ... + Vг-1 < Щ + 42 + ... + Щ-1,

где £ - наибольшая из длин разбиений и и V. Отношение < называют отношением доминирования. В работе [43] показано, что все разбиения числа п образуют решетку относительно < .

В работе [44] отмечено, что все разбиения фиксированной длины числа п образуют решетку относительно <, а также введено понятие элементарного преобразования. Разбиение V = (у1,у2, ... есть результат применения элементарного преобразования к разбиению и = (и1,и2,... ,щ), если найдутся такие натуральные числа г и ], что

1) 1 < %<2 < ¿,

2) щ — 1 ^ и+\ и ^ и^ + 1,

3) щ — и^ = 5 ^ 2,

4) = щ — = и^ + 1,ик = Ук для всех к = 1, 2,... ,1, к = г,].

В работе [44] доказано, что V < и выполняется в том и только в том случае, когда разбиение V может быть получено из разбиения и последовательным применением некоторого конечного числа элементарных преобразований.

Рассмотрим произвольный полный многодольный граф К(щ,и2,... ,щ), где Щ ^ и2 ^ ... ^ иг, и обозначим п = и1 + и2 + ... + иг. Отметим, что последовательность и = (щ,и2,... ,щ, 0,0,0,...) есть разбиение числа п. Таким образом, установлено взаимно-однозначное соответствие между всеми полными ¿-дольными графами на п вершинах и разбиениями длины £ числа п. В дальнейшем, для краткости мы будем обозначать К (щ,и2,... ,щ) через К (и), где и = (щ,и2,... ,щ).

Предположим, что каждому графу С приписано некоторое число а(С). Число а(С) называется хроматическим инвариантом, если оно одинаково для всех хроматически эквивалентных графов. Хорошо известно (см. [6, 13, 14]), что хроматическими инвариантами являются число вершин, число ребер и число треугольников, содержащихся в графе С. Число ребер графа С будем обозначать через 12(С), а число треугольников — через 13(С).

Через рЬ(С, г) обозначим число разбиений множества вершин графа С на г непустых коклик, т. е. подмножеств, состоящих из попарно несмежных вершин. По теореме Зыкова (см. [6]), хроматический многочлен графа С можно представить в виде

п

р (с,х) = ^ Рг(с,1)х(г),

г=Х

где через х(г) обозначена факториальная степень переменной х, т. е. х(г) = х(х — 1) • • •... • • • (х — г + 1). В силу указанной теоремы числа рЬ(С, г) являются хроматическими инвариантами.

В дальнейшем нас особенно будет интересовать инвариант рЪ(С, х + 1), который мы будем обозначать просто через рЪ.

Приведем схему рассуждений, которую мы будем использовать при доказательстве хроматической определяемости полного многодольного графа К (и). Мы будем предполагать от противного, что граф К (и) не является хроматически определяемым. Это означает, что найдется такой граф Н, неизоморфный графу К (и), что Р (Н,х) = Р (К (и),х). Следовательно, граф Н тоже должен содержать п вершин и быть ¿-раскрашиваемым. Это означает, что граф Н может быть получен из некоторого полного ¿-дольного графа К (у) с помощью удаления некоторого множества ребер Е. В работе [47] было доказано, что различные полные многодольные графы не являются хроматически эквивалентными, следовательно, множество ребер Е непусто. Затем, исследуя возможные наборы ребер Е, мы будем получать противоречия и этим завершать доказательство хроматической определяемости графа К (и).

Исследуем как меняются хроматические инварианты 12,13 и вдоль решетки ЫРЬ(п,1) при удалении множества ребер Е из полного многодольного графа.

Зафиксируем три разбиения числа п. Пусть

и = (и1,и2,... ,щ), и' = (и1,и2,... ,щ — 1,щ+1,..., + +1,... ,щ),

V = (У1,У2, .. .,Уг).

Отметим, что и' есть результат элементарного преобразования разбиения и.

Предположим так же, что граф Н получен удалением множества ребер Е из полного многодольного графа К (у).

Рассмотрим инвариант 12. Поскольку 12 — это число ребер, получаем

■•'■«-»-^г- ©—(?)—V—■■■—(:•)■

Следующая лемма устанавливает, как меняется инвариант 12 при элементарном преобразовании.

Лемма 1 ([35, Лемма 1]). А12(К(и), К(и')) = и^ — щ + 1.

Ясно, что при удалении множества ребер Е из графа К (у) число ребер уменьшается на 1Е|, поэтому А12(К(у),Н) = 1ЕI.

Рассмотрим инвариант 13. Любой треугольник в К (у) устроен следующим образом: он имеет по одной вершине из трех различных долей этого графа. Следовательно, 13(К(и)) = ^ и&щит. Следующая лемма устанавливает,

как меняется инвариант 13 при элементарном преобразовании. Лемма 2 ([35, Лемма 2]). А13(К(и), К(и')) = — (щ — щ — 1)(п — щ — щ). Исследуем как изменяется инвариант 13 при переходе от графа К (у) к графу

Н.

Заметим, что при удалении ребер не может образовываться новых треугольников, поэтому для вычисления 13(Н) достаточно вычислить число треугольников, разрушающихся при удалении множества ребер Е.

Пусть / — это произвольное ребро из Е. Обозначим через ) число треугольников из К (у), которые содержат ребро /. Положим ^ = ^ £1(/).

/ еЕ

Рассмотрим произвольный треугольник в К (у). Обозначим его ребра через /ь/2 и /3. Будем говорить, что ребра /1 и /2 порождают ^-подграф, если /ъ/2 е Е и /3 е Е. Обозначим число ^2-подграфов через £2. Другими словами, ^2 — это число треугольников в К (у), у которых ровно два ребра лежит в множестве Е.

Обозначим число треугольников, у которых все три ребра лежат в Е через £з. Ясно, что А 1з( К (у), Н ) = & — & — 2&.

Исследуем изменения инварианта . Любое разбиение множества вершин графа К (и) на 1 + 1 коклику получается разбиением некоторой доли на два непустых подмножества. Долю и\ можно разбить на два непустых подмножества 2Щ — 1 способом, поэтому

рЪ(К (и)) = £ 2м*—1 — г. (1.1)

к=1

Из этого следует, что

АрЪ(К (и), К (и')) = 2Щ—2 — 2й*—1. В работе [46] была

получена оценка

1ЕI < Ар^ Н, К (у)) < 2Е 1 — 1. (1.2)

Другие оценки изменения инварианта р1 при переходе от графа К (у) к графу К(Н) будут установлены в главе 2, здесь же мы приведем одно утверждение, связывающее инвариант и решетку разбиений натуральных чисел.

Лемма 3. Пусть

и = (и1,... ,щ,... ,.. .иг) ^ и' = (... ,щ — 1,... + 1,...)

— элементарное преобразование разбиения и, где щ ^ 2. Если граф Н получен удалением некоторого непустого множества ребер Е из графа К (и), то графы К (и) и Н не являются хроматически эквивалентными.

Доказательство. От противного предположим, что К (и) и Н хроматически эквиваленты. Пусть 6 = щ — и^ ^ 2. Тогда по лемме 1 число удаленных ребер равно 1ЕI = 5 — 1 = щ — и^ — 1 ^ 1.

Вычисляя разность инвариантов и используя неравенство 1.2, получаем 2т—1 + 2и*—1 — 2Щ—2 — 2и* = 2Щ—2 — 2и*—1 ^ 21е 1 — 1 = 2щ—из—1 — 1. Полагая х = 2Щ—2 и у = 2йэ—1, получаем

х 2^—2

и* — 1

_ 2Ui—Uj — 1

У 2

X

х — у ^--1,

У

ху — у2 ^ х — у, х(у — ^ < У(У — 1).

С учетом того, что и^ ^ 2, получаем у = 2й?—1 ^ 2.

Тогда эквивалентными преобразования получаем цепочку неравенств

ж < у, 2Щ—2 < 2и>—1, иг — 2 < щ — 1, иг — щ — 1 < 0, пришли к противоречию. □

При исследовании хроматической определяемости полных трехдольных графов мы будем существенно использовать решетки ЫРЬ(п, 3). Кратко опишем их устройство, более подробное описание может быть найдено в работах [44] и [35].

Ясно, что минимальным элементом в такой решетке будет разбиение, у которого разница между наибольшим и наименьшим ненулевыми членами минимальна. Заметим, что вид минимального элемента зависит от того, какой остаток при делении на 3 дает число п. Положим п = 3д + г, где г — остаток при делении п на 3. Таким образом,

1) если г = 0, то минимальное разбиение имеет вид (д,д,д);

2) если г = 1, то минимальное разбиение имеет вид (д + 1,д,д);

3) если г = 2, то минимальное разбиение имеет вид (д + 1,д + 1,д).

Теперь опишем процедуры получения следующих этажей в этой решетке. В работе [44] было показано, что соотношение и < V тогда и только тогда, когда и может быть получено цепочной элементарных преобразований разбиения V. Таким образом, чтобы получить верхние этажи решетки, достаточно последовательно применять преобразование, обратное к элементарному преобразованию, начиная с минимального элемента решетки.

Список литературы диссертационного исследования кандидат наук Гейн Павел Александрович, 2022 год

ЛИТЕРАТУРА

[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. 618-718.

[3] Dong F.M., Koh K.M, Teo K.L. Chromatic polynomials and chromaticity of graphs. - World Scientific, 2005. - 356 p.

[4] Reed, R. C. An introduction to chromatic polynomials //J. Comb. Theory. - 1968. - Vol. 4. - P. 52-71.

[5] Whitney, H. A logical expansion in mathematics. // Bulletin American Mathematical Society. - 1932. - Vol. 38. - P. 572-579.

[6] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, алгоритмы, матроиды. - Спб.:Издательство "Лань", 2010.- 368с.

[7] Матиясевич Ю. В. Об одном представлении хроматического многочлена // Дискретный анализ. - 1977. - Т. 31. - С. 61-70.

[8] Зыков А. А. О некоторых свойствах линейных комплексов. // Математический сборник. - 1949. Т. 24, №2. - С. 163-188.

[9] Chao, C.Y., Whitehead Jr., E.G. On chromatic equivalence of graphs. In: Theory and applications of graphs (Proc. Internath. Conf., Western Mich. Univ., Kalamasoo, 1976). - Lecture Notes in Math.,. Vol. 642, P. 121-131. — Springer, 1978.

[10] Chao, C.Y., Whitehead Jr., E.G. Chromaticity of self-complementary graphs // Arch. Math. (Basel) - 1979. - Vol. 32. - P. 295-304.

[11] Chao, C.Y., Whitehead Jr., E.G. Chromatically unique graphs // Discrete Math. 1979. - Vol. 27. - P. 171-177.

[12] Chao, C.Y., Zhao, L.C. Chromatic polynomials of a family of graphs // Ars Combin. - 1983. - Vol. 15. - P. 111-129.

[13] Farrell E. J.. On chromatic coefficients. // Discrete Math. - 1980. - №29. -P. 257-264.

[14] Баранский, В.А., Вихарев, С.В. О хроматических инвариантах двудольных графов // Изв. Урал. гос. ун-та. Математика и механика. - 2005.

- Вып. 7, №36. - С. 25—34.

[15] Loernic, B., Whitehead Jr., E.G. Chromatic polynomials for regular graphs and modified wheels //J. Combin. Theory Ser. B. - 1981. - Vol. 31, No 1. -P. 54-61.

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

[17] Salzberg, P.M., Lopez, M.A., Giudici, R.E. On the chromatic uniqueness of bipartite graphs // Discrete Math. - 1986. - Vol. 3. - P. 285-294.

[18] Tomescu, I. On 3-colorings of bipartite p-threshold graphs //J. Graph Theory.

- 1987. - Vol. 11. - P. 327-338.

[19] Koh K.M, Teo K.L.. The search of chromatically unique graphs // Graphs Combin. - 1990. - Vol. 6. - P. 259-285.

[20] Dong F. M. On Chromatic Uniqueness of Two Infinite Families of Graphs // Journal of Graph Theory. 1993. — Vol. 17. — P. 387-392.

[21] Chia, G.L., Ho, C.K. On the chromatic uniqueness of edge-gluing of complete bipartite graphs and cycles // Ars Combin. 2001. — Vol. 60. — P. 193-199.

[22] Zou, H.W. Chromatic uniqueness of certain bipartite graphs К(m,n) — A, (IAI ^ 2) (Chinese) // Tongji Daxue Xuebao Ziran Kexue Ban. 2002. — Vol. 8. — P. 1014-1018.

[23] Peng, Y.H., Rolsan, H. Chromatic uniqueness of certain bipartite graphs with six edges deleted // Thai J. Math. — 2010. — Vol. 8, No 2. — P. 339-354.

[24] Rolsan, H., Peng, Y.H. Chromatic uniqueness of complete bipartite graphs with certain edges deleted // Ars Combin. — 2011. — Vol. 98. — P. 203-213.

[25] Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph K (n — k;n;n) (Chinese) //J. Shanghai Teachers Univ. (Natural Sc.) — 1999.

— Vol.1. — P. 15-22.

[26] Zou, H.W. The chromatic uniqueness of complete tripartite graphs K(ni;n2]n3) (Chinese) // J. Sys. Sci. Math. Sci. — 2000. — Vol. 20. — P. 181-186.

[27] Zou, H.W. The chromatic uniqueness of certain complete tripartite graphs K(m; n; r) // J. Math. (Wuhan) — 2003. — Vol. 23. — P. 307-314.

[28] Zou, H.W. The chromaticity of the complete tripartite graph K(n — 4; n; n) (Chinese) //J. Shanghai Teachers Univ. (Natur. Sci.) — 1998. — Vol. 1. P. 37-43.

[29] Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph K (n;n;n + k) (Chinese) //J. Shanghai Teachers Univ. (Natur. Sci.). — 2000.

— Vol. 3. — P. 29-35.

[30] Liu R., Zhao H., Ye C. A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. // Discrete Mathematics. - 2004. -№289. - P. 175—179.

[31] Chia G.L., Ho C.-K. Chromatic equivalence classes of some families of complete tripartite graphs. // Bulletin of the Malaysian Mathematical Sciences Society. - 2014. - №37. - P. 641-646.

[32] Giudici, R.E., Lopez, M.A., Salzberg, P.M. Chromatic uniqueness for some bipartite graphs Km^n (Spanish) // Acta Cient. Venezolana 1986. Vol. 37. P. 484-494.

[33] Zhao H. Chromaticity and adjoint polynomials of graphs. - Zutphen: Wohrmann Print Service. - 2005. - 169 p.

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

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

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

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

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

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

[40] Li, N.Z., Liu, R.Y. The chromaticity of the complete ¿-partite graph К(1;p2;...;pt). // Xinjiang Univ. Natur. Sci. 1990. Vol. 7, No 3. P. 95-96.

[41] Эндрюс, Г. Теория разбиений. — М.: Наука, 1982. 256 с.

[42] Andrews, G., Erikson, K. Integer Partitions. - Cambridge University Press, 2004. 141 p.

[43] Brylawski, T. The lattice of integer partitions. // Discrete Mathematics. -1973. - №6. - P. 210-219.

[44] Baranskii V.A., Koroleva T.A., Senchonok T.A On the partition lattice of all integers. // Sib. Elektron. Mat. Izv. - 2016. - №13. - P.744-753.

[45] Dong F. M., Koh. K. M., Teo K. L., Little C. H. C., Hendy M. D..

Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs. // Journal of Graph Theory. - 2001. - Vol. 37, №1. - P. 48-77.

[46] Zou, H. W. The chromatic uniqueness of certain complete ¿-partite graphs. // Discrete Mathematics. - 2004. - №. 275. - P. 375-383.

[47] Zhao H. et al. On the minimum real roots of the ^-polynomials and chromatic uniqueness of graphs. // Discrete mathematics. - 2004. - №281. - P. 277-294.

[48] Chia G.L., Ho C.-K. Chromatic equivalence classes of complete tripartite graphs. // Discrete Mathematics. - 2009. - №309. - P. 134--143.

[49] Gein P. A. About chromatic uniqueness of complete tripartite graph K(s, s — 1,s — k), where k ^ 1 and s — k ^ 2. // Siberian Electronic Mathematical Reports. - 2016. - Vol. 13, №1. - P.331-337.

[50] Gein P. A. About chromatic uniqueness of some complete tripartite graphs. // Siberian Electronic Mathematical Reports. - 2017. - Vol. 14, №1. - P.1492-1504.

[51] Gein P. A. On garlands in %-uniquely colorable graphs // Siberian Electronic Mathematical Reports. - 2019. - Vol. 16, №1. - P.1703-1715.

[52] Gein P. A. About chromatic uniqueness of some complete tripartite graphs. // Ural Mathematical Journal. - 2021. - Vol. 7, №1. - P. 38-65.