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

Одна из наиболее известных задач теории графов — проблема четырех красок. Имеются сведения, что Мёбиус был знаком с этой проблемой в 1840 г., и достоверно известно, что Гутри сообщал де Моргану о данной проблеме в 1850 г. Первое из многих ошибочных доказательств было дано Кемпе [1] в 1879 г. Ошибку в доказательстве Кемпе в 1890 г. обнаружил Хивуд [2], который тогда же установил, что гипотеза верна, если «четыре» заменить на «пять». Иными словами, Хивуд доказал, что любой планарный граф раскрашивается в пять красок.

В 1969 г. проблема четырех красок была сведена X. Хе-ли к рассмотрению весьма большого конечного числа случаев. Наконец, в 1976 г. Аппелль и Хейкен решили проблему четырех красок, но, возможно, не самым лучшим способом. Решение потребовало длительного перебора компьютером огромного числа случаев. Сам факт компьютерного решения проблемы четырех красок является, несомненно, выдающимся достижением, которое вполне достаточно для прекращения поиска контрпримера.

Более чем столетняя история попыток решения этой проблемы сыграла положительную роль в развитии различных разделов теории графов и особенно для исследования свойств раскрасок графов. Во многих работах было показано важное прикладное значение раскрасок графов для задач теории расписаний, задач экономии памяти, задач распределения ресурсов и многих других задач (см. [3−12]).

Для нас важно отметить, что попытки решить проблему четырех красок привели Биркгофа [13] к понятию хроматического многочлена карты. В работе Уитни [14] это понятие было расширено до понятия хроматического многочлена произвольного графа и получен ряд фундаментальных свойств хроматических многочленов графов. Необходимо также отметить работу Биркгофа и Льюиса [15], в которой были получены некоторые результаты о хроматических многочленах пла-нарных графов и сформулированы нерешенные задачи. Большое значение для исследования хроматических многочленов графов имела обзорная статья Рида [16], в которой были подведены некоторые итоги и сформулированы открытые вопросы. Детальную информацию о современном состоянии теории хроматических многочленов графов можно найти в обзорных статьях [17−21] и монографиях [22] и [23].

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

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

Пусть С — произвольный (гг, гтг, к)-граф, т. е. граф, имеющий п вершин, т ребер и к компонент связности. Раскраской, или ¿—раскраской графа С называется отображение ф из множества вершин V в множество натуральных чисел {1, 2,., ?} такое, что для любых двух различных смежных вершин и и V графа С? выполняется ф{и) ф Ф{у), т. е. любые две различные смежные вершины имеют разный «цвет». Граф называется раскрашиваемым, если он обладает ¿—раскраской и — Ахроматическим, если он ¿—раскрашиваемый, но не является (? — 1)-раскрашиваемымв этом случае число? называется хроматическим числом графа С* и обозначается через.

Для натурального числа х через Р (С, х) обозначим число всевозможных раскрасок графа (3 в х заданных цветов, причем не предполагается, что в раскраске должны быть использованы все х цветов. Хорошо известно (см. [16] или [24]), что функция .Р (бг, х) является многочленом степени п от х, который называют хроматическим многочленом графа (?. Два графа называются хроматически эквивалентными, или х~эк~ вивалентнымщ если они имеют одинаковые хроматические многочлены.

Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвариантами являются число вершин, число ребер и число компонент связности графа (см. [16] или [24]). Число ребер графа (3 будем обозначать через /2©. Отметим, что число вершин графа (2 можно было бы обозначать через 1{0).

Укажем еще два хроматических инварианта для графов (см. [25] или [26]):

1 г (С)=А (0) — число треугольников в графе.

14(0) = идП (С)-2Ы ©, где через vg П (G) мы обозначаем число вершинно порожденных подграфов вида Щ в графе G, т. е. число бесхордных 4-циклов в G, а через М (G) — число полных четырехвершин-ных подграфов в графе G.

Через pt (G, г) будем обозначать число разбиений множества вершин графа G на г непустых коклик, т. е. подмножеств, состоящих из попарно несмежных вершин графа G. По теореме Зыкова (1952) (см. [27] или [28]) п г=Х где через х^ обозначается факториалъная степень переменной х, т. е. х^ — х (х — 1)(ж — 2). (х — i + 1), а через % —хроматическое число графа G. В силу указанной теоремы числа pt (G, i) при х < & < п являются хроматическими инвариантами.

Граф называется хроматически определяемым, или х~опРе~ деляемым, если он изоморфен любому хроматически эквивалентному ему графу. Это понятие ввели в 1976 г. Chao С.Y. и E.G. Whitehead Jr. [29]. Различными авторами были проведены многочисленные исследования по изучению хроматической эквивалентности и хроматической определяемости для графов. В этих исследованиях большое место было уделено изучению хроматической определяемости полных многодольных графов.

Граф G называют двудольным графом, если множество его вершин можно разбить на два непустых подмножества (доли) так, что любое ребро данного графа соединяет вершину из одной доли с вершиной из другой долиесли каждая вершина из одной доли соединена с каждой вершиной из другой доли, то G называют полным двудольным графом.

Граф G называют t-дольным графом, если множество его вершин можно разбить на t непустых подмножеств (долей) так, что-любое ребро данного графа соединяет вершину из одной доли с вершиной из другой долиесли каждая вершина из одной доли соединена с каждой вершиной из других долей, то G называют полным t-долъным графом и обозначают через К (щ, п2,., щ), где ni, П2,., nf — последовательность чисел элементов для всех t долей этого графа.

В 1990 г. Koh K.M. и Тео K.L. [18] доказали, что полный двудольный граф К (п1,п2) хроматически определяем при п > 77−2 > 2.

Следующие полные трехдольные графы хроматически определяемые (см. [30−34] и [23]).

1. Граф К (п — к, п, п) при п > к + у.

2. Граф К (п, n, п + к) при п >

3. Граф К (п — k, n, п + к) при п > к2 + ^к.

4. Граф К (п — 4, п, п) при п > 6.

5. Граф К{п — /г, п, тг) для любых целых чисел п и к таких, что п > к + 2 > 4.

6. Граф К (п — k, п — 1, тг) для любых целых чисел пик таких, что п > 2к > 4.

Следующие полные многодольные графы хроматически определяемые (см. [35−37] и [23]).

7. Граф К (п1,П2,. ¦, nt), если щ — щ < 1 для всех i: j = 1,2.

8. Граф К (п — 1, п,., га, га + 1) при t > 2 и п > 3.

9. Граф К (1, П2,., щ) тогда и только тогда, когда max{ni, п-2, ¦ • ¦, nt} < 2.

10. Граф К (п — к, га, га,., га) для любых положительных целых чисел га > к 4- 2, к > 2.

11. Граф К (п — к, га — 1, га,., га) для любых положительных целых чисел га > 2к, к > 2.

12. Граф K (ni, щ,.), если |raj —га^| = 2 и mm{ni, пг,., nj >i + l.

Основной вопрос состоит в следующем: является ли хроматически определяемым полный многодольный граф К (п 1, га2,., nt) при i > 3 и ni > n . > тгг > 2?.

Цель данной работы:.

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

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

Перейдем теперь к изложению основных результатов диссертации. Текст диссертации, следующий за введением, разделен на три главы. Основные результаты работы названы теоремами, их четыре и они имеют сквозную нумерацию..

Первая глава посвящена описанию некоторой новой решетки разбиений натуральных чисел. Понятие разбиения натурального числа впервые появилось в 1669 году в письме Лейбница к Иоганну Бернулли. Основы же теории разбиений чисел были заложены Эйлером. В монографии [39] можно ознакомиться с историей этой теории и многочисленными ее достижениями..

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

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

На указанной диаграмме представлено разбиение 19 = 6 + 4 + 4 + 2 + 1 + 1 + 1 числа 19 на 7 слагаемых. Здесь 7 — длина разбиения (6,4, 4, 2,1,1,1)..

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

Потенциалом диаграммы назовем сумму потенциалов всех ее блоков. Потенциал диаграммы, изображающей разбиение и, обозначим через J (u)..

Через NPL, NPL (n), NPL (n, t), NPL (n, s. t), где 1 < s < t <п, обозначим соответственно множество всех разбиений всех натуральных чиселмножество всех разбиений натурального числа пмножество всех разбиений длины t натурального числа пмножество всех разбиений длины I натурального числа п, для которых s < I < t..

Введем понятие элементарного преобразования разбиения u — (iii, ii2,., щ) числа п = num (u). Предположим, что существуют натуральные числа i, j Е {1, 2, .,?}, г < j такие, что.

1) Ui — 1 > щ+1 и Uj-1 > Uj + 1-.

2) щ — щ + где 6 > 2..

Будем говорить, что разбиение v = (щ, ., щ—1,., Uj+1, ., щ) получено элементарным преобразованием (или перекидыванием блока) разбиения и = (щ, W2,.., uj,., ut). Отметим, что v отличается от и точно на двух компонентах с номерами г и j. Для диаграммы Ферре такое преобразование означает перемещение верхнего блока г-го столбца вправо в j-ый столбец. Условия 1) и 2) гарантируют, что после такого перемещения снова получится диаграмма Ферре..

Введем отношение > на множестве NPL (n), полагая и > v для и, v G NPL (n), если v можно получить из и с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований..

Заметим, что после применения элементарного преобразования потенциал диаграммы уменьшается на o — 1, так как на.

6 — 1 уменьшается число блоков, находящихся под перемещаемым блоком. Следовательно, если и, V? Л^РЬ{п) и и > V, то Ли) > Л1″).

Теперь ясно, что отношение > на множестве ЫРЬ{п) является отношением частичного порядка..

На множестве ЫРЬ (п) зададим еще одно отношение !>, полагая и Е> у в случае, если.

Щ > У Щ + и2 > г?1 + и2 г¿-l + г¿-2 +. + щ > VI + у2 +. + VI.

Щ + г¿-2 +. + Щ-1 > VI + г>2 +. + г>г1, где и = (щ, и2,., щ), V = (^1,^2, -. •, г>г), t — максимальная из длин и и V. Конечно, здесь выполняется щ + и2 +. + щ — п = VI + У2 + .+ Vt к щ + и2 + .+ Щ = VI + У2 + .+ у3 при в > Поэтому условие, задающее отношение О, эквивалентно условию ^1+^2+ • ¦ • +щ > г71+г>2+. -Нг^ (г=1, 2,3,.). Теперь рефлексивность, антисимметричность и транзитивность отношения > очевидны, т. е. является отношением частичного порядка на МРЬ{п)..

Во втором параграфе главы 1 доказано, что отношения > и ^ совпадают на ЛгРЬ (п)..

Первый основной результат главы 1 — следующая.

Теорема 1. Множество NРЬ (п) является решеткой относительно отношения >..

Эту решетку мы будем называть решеткой разбиений натурального числа п. Во втором параграфе указаны быстрые алгоритмы нахождения пересечения и объединения в решетке NPL (n)..

Устройство решетки NPL{9) продемонстрировано на Рис. 1, здесь через m х к, где т, к — натуральные числа, мы обозначаем последовательность, составленную из к экземпляров числа т..

Ч (9).

3,3, ЗК М5,1×4).

3, 2,1×4) (3,1×6) ф, 2,1×5) ' (2,1×7).

1x9) рис. 1 NPL{ 9).

Рассмотрим теперь множество NPL всех разбиений всех натуральных чисел. Легко видеть, что множество NPL равно дизъюнктному объединению множеств NPL (n), где п — 1,2,..

В число элементарных преобразований разбиений из АТРЬ включим все элементарные преобразования разбиений из множеств вида АТРЬ (п) и добавим новые, которые будем называть удалениями блоков..

Пусть и = (и1,и2,.) е ИРЬ и щ — 1 > щ+1. Преобразование, которое заменяет и на и' = (и, щ,., 1, щ — 1, щ+1, щ+2, • •.) будем называть удалением блока..

На множестве АТРЬ определим отношение р, полагая ири, если V можно получить из у с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований всех рассмотренных типов. Очевидно, р является отношением частичного порядка и для любого натурального п на множестве Атрь{п) С АТРЬ отношение р совпадает с ранее рассмотренным отношением >, так как из пит (и) = пит{у) и иру следует и > V. В силу этого отношение р далее будем обозначать через >..

Отношения !>, определенные нами на всех А? РЬ (п), продолжим на АТРЬ, полагая и = (глх, гхг, • • •) ^ V = (^ъ • • •)> если щ + и2 +. + щ > VI + г>2 + • • • + VI (г — 1,2,.)..

Отношение О, очевидно, является отношением частичного порядка на ИРЬ и его ограничение на любом АТРЬ{п) совпадает с >..

В третьем параграфе главы 1 установлено, что отношения > и !> совпадают на ИРЬ..

Второй основной результат главы 1 — следующая.

Теорема 2. Мноэюество ЫРЬ является решеткой относительно отношения >..

Эту решетку мы будем называть решеткой разбиений натуральных чисел. Мы установим, что любая решетка АТРЬ (п) является подрешеткой решетки ИРЬ и решетка АТРЬ равна специальным образом устроенному дизъюнктному объединению таких подрешеток..

Устройство нижней части решетки ЫРЬ продемонстрировано на Рис. 2..

На множестве АТРЬ хорошо известны два других решеточных порядка — порядок Юнга, дающий решетку Юнга [38], и лексикографический порядок..

Пусть и = (и, и2> • • = (VI, .) — два разбиения из АТРЬ. Порядок Юпга иУ V определяется условием щ > VI, и2 >У2,..

Очевидно, ИРЬ, является решеткой, которую называют решеткой Юнга. Из определения порядка Юнга следует щ + 42 +. + щ > VI + г>2 + • • - + VI {% — 1,2,.), т. е. введенный нами порядок > на ЫРЬ продолжает порядок Юнга..

Нетрудно заметить, что наш порядок на АТРЬ продолжается до лексикографического порядка..

Далее мы применим решетки ЫРЬ (п) для изучения хроматических многочленов графов. Собственно, изучение свойств хроматических многочленов графов и привело нас к идее рассмотрения указанных решеток. Мы уверены, что эти решетки будут полезны в различных исследованиях, где используются разбиения натуральных чисел и есть необходимость их сравнения. Вероятно, порядок > является наиболее естественным порядком для разбиений чисел..

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

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

Пусть п — щ + П2 +. + nt, где щ > п2 >. > nt,> 1, — разбиение числа п. Через K (jii, П2,., тц) будем обозначать полный í—дольный граф на п вершинах с долями размеров Щ, П2, • ¦ • 5 ntЯсно, что с точностью до изоморфизма существует взаимно однозначное соответствие между полными í—дольными графами на п вершинах и элементами решетки NPL (n, t). Поэтому порядок < на NPL (n, t) индуцирует отвечающий ему порядок на множестве таких графов. Мы можем отождествлять полный многодольный n-граф с соответствующим разбиением числа п..

Пусть п и t — фиксированные натуральные числа, такие, что 3 < t < п. Разделим п на t с остатком: п — t • q + г, где О < г < t..

В 1982 г. Chao C.Y. и G.A. Novacky Jr. [35] доказали, что хроматически определяются полные t-дольные n-графы вида K (q + 1,., q + 1, q,., q), где компонента q + 1 повторяется г раз, а компонента q повторяется s = t — г раз. Иными словами, полные многодольные графы, являющиеся наименьшими элементами в решетках NPL (n, t), хроматически определяются. Далее мы приведем очень простое доказательство этого утверждения (см. Предложение 5.1)..

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

Теорема 3. Пусть {п, п2,., nt) — разбиение, являющееся атомом решетки разбиений натурального числа п на t слагаемых, где rix > п2 >. > щ > 2 и t > 3. Тогда полный многодольный граф К (п, п2, • ¦ ¦, щ) хроматически определяется..

Отметим, что частный случай теоремы при г = 0 был получен в 1988 г. Giudici R.E. и Lopez М.А. [36] (см. также (8) на стр. 5). Другой частный случай следует из результата Zhao Н.Х. [23] (см. также (12) на стр. 6), но при условии q > t + 2..

Третья глава посвящена изучению хроматической опреде-ляемости полных трехдольных графов, находящихся на нижних «этажах» решеток NPL (n, 3). Основной результат главы 3 — следующая.

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

Отметим, что данная теорема обобщает и усиливает ряд результатов, указанных на стр. 7. Возникающие здесь конкретные случаи описаны в главе 3..

1. Оре, О. Графы и их применение. — М.: Мир, 1965..

2. Оре, О. Теория графов и ее применения. — М.: Наука, 1980. Рейнгольд, Э., Нивергельт, Ю., Део, Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980..

3. Свами, М., Тхуласираман, К. Графы, сети и алгоритмы. — М.: Мир, 1984..

4. Татт, У. Теория графов. — М.: Мир, 1988..

5. Уилсон, Р.

Введение

в теорию графов. — М.: Мир, 1977..

6. Харари, Ф. Теория графов. — М.: Мир, 1973..

7. Birkhoft, 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..

8. Whitney, H. The coloring of graphs // Annal. Math., 1932. Vol. 33. P. 688−718..

9. Birkhoft, G.D., Lewis, D. Chromatic polynomials // Trans. Amer. Math. Soc., 1946. Vol. 60. P. 355−451..

10. Read, R.C. An introduction to chromatic polynomials //J. Comb. Theory, 1968. Vol. 4. P. 52−71..

11. Read, R.C., Tutte, W.T. Chromatic polynomials. — In: Selected Topics in Graph Theory III. Academic Press. 1988..

12. Koh, K.M., Teo, K.L. The search for chromatically unique graphs // Graphs Combin., 1990. Vol. 6 P. 259−285..

13. Koh, K.M., Teo, K.L. The search for chromatically unique graphs II // Discrete Math. 1997. Vol. 172. P. 59−78..

14. Chia, G.L. Some problems on chromatic polynomials // Discrete Math. 1997. Vol. 172. P. 39−44..

15. Liu, R.Y. Adjoint polynomials and chromatically unique graphs // Discrete Math. 1997. Vol. 172. P. 85−92..

16. Dong, F.M., Koh, K.M., Teo, K.L. Chromatic polynomials and chromaticity of graphs. — Monograph, Preprint, 2004..

17. Zhao, H. Chromaticity and adjoint polynomials of graphs. — Wohrmann Print Service, The Netherlands, 2005..

18. Асанов, M.O., Баранский, В.А., Расин, B.B. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001..

19. Farrell, E.J. On chromatic coefficients // Discrete Math. 1980. Vol. 29. P. 257−264..

20. Баранский, В.А., Вихарев, C.B. О хроматических инвариантах двудольных графов // Известия Уральского гос. университета, 2005. Математика и механика. Вып. 7. № 36. С. 25−34..

21. Зыков, A.A. Теория конечных графов. — Новосибирск: Наука, 1969..

22. Зыков, A.A. Основы теории графов. — М.: Наука, 1987..

23. Chao, C.Y., E.G. Whitehead, Jr. 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..

24. Zou, H.W. The chromaticity of the complete tripartite graph К{п—Ащп) (Chinese) //J. Shanghai Teachers Univ. (Natur. Sei.) 1998. Vol. 1. P. 37−43..

25. Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph K (n — knn) (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 (n in2- n3) (Chinese) //J. Sys. Sei. Math. Sei. 2000. Vol. 20. P. 181−186..

27. Zou, H.W., Shi, Y.B. On the chromaticity of the complete tripartite graph К{п]щп + k) (Chinese) //J. Shanghai Teachers Univ. (Natur. Sei.) 2000. Vol. 3. P. 29−35..

28. Zou, H.W. The chromatic uniqueness of certain complete tripartite graphs К (тщг) // J. Math. (Wuhan) 2003. Vol. 23. P. 307−314..

29. Chao, C.Y., G.A. Novacky, Jr. On maximally saturated graphs // Discrete Math. 1982. Vol. 41. P. 139−143..

30. Giudici, R.E., Lopez, M.A. Chromatic uniqueness of sKn) Report No. 85−03, Dpto. de Mat. у Ciencia de la Comp. Univ. Sim. on Bolivar, 1985.

31. Li, N.Z., Liu, R.Y. The chromaticity of the complete t-partite graph K (l]p2]. -pt) // JXinjiang Univ. Natur. Sei. 1990. Vol. 7. No.3. P. 95−96..

32. Айгнер, M. Комбинаторная теория. — M.: Мир, 1982..

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

34. Гретцер, Г. Общая теория решеток. — М.: Мир, 1982..

35. Баранский, В.А., Королева, Т. А. Хроматическая определяемость атомов в решетках полных многодольных графов // Труды Института математики и механики УрО РАН. 2007. Том 13, № 3. С. 22−29..

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

37. Баранский, В.А., Королева, Т. А. Решетка разбиений натурального числа / / Доклады Академии Наук. 2008. Том 418, Ш. С. 439−442..

38. Королева, Т.А. О хроматической определяемости полных трехдольных графов // Труды XXXIX Молодежной конференции. ИММ УрО РАН, Екатеринбург 2008. С. 2327..

39. Королева, Т. А. Хроматическая определяемость некоторых полных трехдольных графов // Сборник тезисов XV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2008». С. 47.9.