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

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

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

Пусть u=(ui,U2,...) Є NPL и щ — 1 > щ₊\. Преобразование, которое заменяет и на и' = (ui, ^2) , Щ-и Щ — 1, Щ+і, щ+2, .) будем называть удалением блока.

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

Отношения !>, определенные нами на всех NPL(n), продолжим на NPL, полагая и = (щ,и2, ) !> v = (vi, г>2, )> если

щ + щ + ... + щ > vi + г>₂ + + Vi (г = 1,2,...).

Отношение !>, очевидно, является отношением частичного порядка на NPL и его ограничение на любом NPL(n) совпадает с >.

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

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

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

Эту решетку мы будем называть решеткой разбиений натуральных чисел. Мы установим, что любая решетка NPL(n)

является подрешеткой решетки NPL и решетка NPL равна специальным образом устроенному дизъюнктному объединению таких подрешеток.

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

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

Пусть и = (щ, U2, ---),^ = (г;і,г>2, ---)^- Д^ва разбиения из NPL. Порядок Юта иУ v определяется условием

щ >vi,u₂ >v₂,..-.

Очевидно, NPL, ^ является решеткой, которую называют решеткой Юнга. Из определения порядка Юнга следует щ + ui + ... + «j > vi + 1 + - - - + Vi (і — 1,2,...), т. е. введенный нами порядок > на NPL продолжает порядок Юнга.

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

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

Л7,1)

{6,2)

«5,1,1)

(5.3)

4,4) ,(4,3,1)

,(4,2,2)

(3,3,2)

^3,2,2,1) (2x4)

(2x3,1x2)

,,(2, 2,1x4)

(2,1x6)

*(1х8)

'(1*7)

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

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

ПуСТЬ П — Щ + П2 + ... + щ, где П\ > п₂ > ... > щ.> 1, — разбиение числа п. Через K(ni,ri2, ,n_t) будем обозначать полный t-дольный граф на п вершинах с долями размеров пі,П2,...,щ. Ясно, что с точностью до изоморфизма существует взаимно однозначное соответствие между полными t-дольными графами на п вершинах и элементами решетки NPL(n, t). Поэтому порядок < на NPL(n, t) индуцирует отвечающий ему порядок на множестве таких графов. Мы можем отождествлять полный многодольный n-граф с соответствующим разбиением числа п.

Пусть п и t — фиксированные натуральные числа, такие, что 3 < 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, ,щ) — разбиение, являющееся

атомом решетки разбиений натурального числа п на t слагаемых, где пі > п₂ > ... > щ > 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.

Решетки NPL(n)

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

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

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

На указанной диаграмме представлено разбиение 19 = 6 + 4 + 4 + 2 + 1 + 1 + 1 числа 19 на 7 слагаемых. Здесь 7 — длина разбиения (6,4, 4, 2,1,1,1). Введем отношение на множестве NPL(n), полагая и v для и, v Є NPL(n), если v можно получить из и с помощью последовательного выполнения конечного числа (возможно нулевого) элементарных преобразований. Заметим, что после применения элементарного преобразования потенциал диаграммы уменьшается на 6 — 1, так как на 5 — 1 уменьшается число блоков, находящихся под перемещаемым блоком. Следовательно, если u,v Є NPL(n) и и v, то J (и) J(v).

Теперь ясно, что отношение на множестве NPL(n) является отношением частичного порядка. Наша цель — установить, что NPL(n) является решеткой относительно . Эту решетку мы будем называть решеткой разбиений натурального числа п. Мы укажем быстрые алгоритмы нахождения пересечения и объединения в решетке NPL{n). Затем введем некоторый естественный порядок на NPL, относительно которого NPL также является решеткой — решеткой разбиений натуральных чисел. Мы установим, что любая решетка NPL(n) является подрешеткой решетки NPL и решетка NPL равна специальным образом устроенному дизъюнктному объединению таких подрешеток.

На множестве NPL хорошо известны два других решеточных порядка — порядок Юнга, дающий решетку Юнга (см. [38]), и лексикографический порядок. Как мы установим в дальнейшем наш порядок на NPL содержит порядок Юнга и содержится в лексикографическом порядке.

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

Пусть у двух каменщиков имеется по собственной стенке (диаграмме Ферре), сложенной из п блоков: (щ,и2,... ,щ) и (vi,v2,. .. ,vt), где щ ф 0 или vt Ф 0. Каждый каменщик перекладывает свою стенку в новую стенку {w\,Wi, ...,), т. е. оба каменщика строят по новой, причем одинаковой, стенке. Они строят новые стенки синхронно по столбцам слева на право. На каждом этапе вначале каждый каменщик имеет запас блоков, оставшихся от предыдущего этапа, и блоки содержащиеся в очередном столбце старой стенки. Из запаса и столбца каждый из них строит новый столбец, который максимален по высоте из допустимых столбцов, т. е. не превосходит по числу блоков число блоков, имеющихся в начале этапа у каждого из каменщиков отдельно. Заметим, что если на некотором этапе один из каменщиков исчерпал все блоки своей стенки, т. е. у него получился нулевой запас и очередной столбец пуст, то и второй каменщик на этом же этапе полностью исчерпал все блоки своей стенки, так как каждая из исходных стенок содержит одинаковое число блоков, равное п. Ясно, что алгоритм закончит свою работу, когда будут исчерпаны все п блоков, поэтому num(w) = п.

Хроматические инварианты

Пусть G — произвольный обыкновенный (п, т, /с)-граф, т. е. граф, имеющий п вершин, т ребер и к компонент связности (без петель и кратных ребер). Для натурального числа х через P(G, х) обозначим число всевозможных раскрасок графа G в х заданных цветов, причем не предполагается, что в раскрас ке должны быть использованы все х цветов. Хорошо известно (см., например, [16] или [24]), что функция P(G,x) является многочленом степени п от х, который называют хроматическим многочленом графа G. Два графа называются хроматически эквивалентными, или х эквивалентными1 если они имеют одинаковые хроматические многочлены. Предположим, что каждому графу приписано некоторым образом число. Это число называют хроматическим инвариантом, если оно одинаково для любых двух хроматически эквивалентных графов. Хроматическими инвариантами являются число вершин, число ребер и число компонент связности графа (см. [16] или [24]). Число ребер графа G будем обозначать через h G). Отметим, что число вершин графа G можно было бы обозначать через I\{G). Укажем еще два хроматических инварианта для графов (см. [25] или [26]): h(G)=A(G) — число треугольников в графе G; U{G) = vgU(G)-2U{G)t где через vg Ц (G) мы обозначаем число вершинно порожденных подграфов вида П в графе G, т. е. число бесхордных 4-циклов в G, а через М (G) — число полных четырехвершин-ных подграфов К в графе G.

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

Ясно, что с точностью до изоморфизма существует взаимно однозначное соответствие между полными t-дольными графами на п вершинах и элементами решетки NPL(n, t). Поэтому порядок на NPL(n, t) индуцирует отвечающий ему порядок на множестве таких графов. Мы можем отождествлять полный многодольный п-граф с соответствующим разбиением числа п.

Используя ранее введенные обозначения и условие IA(G) — h(H), имеем h{H) = h(ni,n2,ns) + rj - гц + r]2 + 2т]3 + З774, т. е. 7-771+ + 2 + З774 = h{u) - h{v). (2.3) Лемма 4.5. Пусть и = (g + аь g + о?2, g + «з) w г; = (g + /Зі, g+/ 2, д+/ з) — произвольные элементы из NPL(n, 3) такие, что q + ai q + fa и q + а3 q + /33, где аь а2, «з, A, /. / — целые числа. Тогда и v. Доказательство. Применим алгоритм 1 вычисления и Л v, указанный в параграфе 2. Очевидно, и Л v = (g + /Зі, ж, g + /) для некоторого натурального числа х. Поскольку uAv — разбиение числа п, отсюда имеем ж = g + /32, т. е. и Л v — v. Следовательно, и v. # Лемма 4.6. Пусть и и v - произвольные несравнимые элементы в iVPL(n, 3). Тогда 12(и) ф I2(v) или 13(и) ф h(v). Доказательство. Ясно, что и= (g + а\, д + а2, q + «з) VLV — (д + /Зі, д + /З2, д + /З3) для некоторых целых чисел ai, а2, аз, /Зі, /32, /Зз. Если g + ai = g + /Зі, то легко понять, что киї; сравнимы. Без ограничения общности будем считать, что g + а?і g + /Зі. Если g + аз = q + Рз, то w и i сравнимы. Поэтому имеем g + 0:3 т 5 + Рз- В силу леммы 4.5 получаем g + аз g + /З3. Используя алгоритм вычисления пересечения, получаем w Л v = (д + /Зі,ж,д + «з) Для некоторого натурального числа ж. Тогда от и до и Л г имеется цепочка элементарных преобразований, осуществляющих падение блока с первой компоненты на вторую. Обозначим через 1\ сумму всех значений 5—1, отвечающих этим преобразованиям. Аналогично, имеется цепочка элементарных преобразований от v до и Л г , осуществляющих падение блока со второй компоненты на третью. Обозначим через 12 сумму всех значений 6—1, отвечающих этим преобразованиям. Тогда І2(и) — І2(иЛv) = —h и I2(v) — I2(uAv) — —l2 на основании леммы 4.1. Пусть выполняется равенство hiu) = h(v). Тогда l\ = l2. В силу леммы 4.2 имеем J3(u) - h(u Л v) = -/1(9 + «з), h{v) - h(u Av) = -l2(q + Pi). Пусть, от противного, h(u) — h(v). Тогда q + аз = q + j3\, т. е. осг — Pi- Последнее равенство невозможно, так как / 0 и а3 0. # Предложение 4.1. Любые два различных полных трехдольных п-графа не являются хроматически эквивалентными. Доказательство. Учитывая лемму 4.6, достаточно заметить, что в силу леммы 4.1 в NPL(n, 3) из условия и v следует Ш h{v).

Атомы в решетках полных многодольных графов

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

Легко видеть, в решетке NPL(n, t) имеется не более двух атомов, т. е. разбиений, покрывающих наименьшее разбиение и — (я + 1) Я + 1) Я-, ) ч)- Эти атомы имеют вид «і = (д +1, я +1, q, q, q - і), (2.4) где компонента q + 1 повторяется г + 1 раз, компонента q повторяется s — 2 раза, и щ = (д + 2, q + 1,..., q + 1, q,..., q), (2.5) где компонента g + 1 повторяется г — 2 раза, а компонента g повторяется s +1 раз. Первый из атомов существует при условии s 2ng 2,a второй — при условии г 2. Отметим, что если 0 г 1, то s = t — г t — 1 2, т. е. если отсутствует атом второго типа, то при g 2 обязательно существует атом первого типа. Лемма 5.1. Пусть в NPL(n,t) существует два атома щ и щ. Тогда соответствующие им полные t-дольные графы К(щ) и K{u2) не являются хроматически эквивалентными. Доказательство. Пусть К(щ) и К{щ) хроматически эквивалентны. Тогда pt(K(ui),t + 1) = pt(K(u2),t + 1) и поэтому (г + 1)29 + (s - 2)2 1 + 2q 2 = 2q+1 + (г - 2)29 + (s + 1)2«-\ т. е. 2q + (s - 2)2 -1 + 2«-2 = (s +1)2 1, откуда следует 2« 2 = 2?-1, что невозможно. # Из лемм 4.1 и 5.1 вытекает Следствие 5.1. Любой полный t-дольный п-граф, являющийся атомом решетки NPL(n,t), хроматически неэквивалентен каждому неизоморфному ему полному многодольному графу.

Предложение 5.1. Граф G = K(q + 1,..., q + 1, g,..., q), где компонента q + 1 повторяется г раз, а компонента q повторяется s раз, является х-определяемым при q 1. Доказательство. Пусть G = -К"(г і), где tti — атом (2.4). Тогда для Я" в силу леммы 4.1 имеем v = (пі,П2,... ,nf) = (9 + 1,..., q + 1, 9, 9), где компонента 9 + 1 повторяется г раз, а компонента q — s раз. Здесь е = 1 и поэтому 2 = з = 0. Следовательно, 1 = -(/3( 1) — /3(f)) = ( — 1)(п — (9 + 1) — (9 — 1)) = n—2q. С другой стороны, = п—щ—rij для некоторых г, Є {1,2,..., t} и г 3- Отсюда следует, что щ = щ = q. Таким образом, удаляемое ребро соединяет две вершины из долей, содержащих по q элементов.

Заметим теперь, что 4-клики в Н устроены следующим образом причем при переходе от К{п\,п2,..., щ) разрушаются 4-клики, содержащие ребро / из Е. Обозначим через В2 число способов выбора двух вершин по одной из двух различных неособых долей, а через В% — число способов выбора трех вершин по одной из трех различных неособых долей. Тогда ЩН)-Щв) = qqB2-B2 + 2qB3-(q+l)(q-l)B2-{q+l)B3-(q-l)B3 = (ql-l-(q+l)(q-l))B2+(2q-(q+l)-(q-l))B3 = 0. Таким образом, I4(H) - IA{G) = -(q 1}2(q"2). Так как q 3, получаем h(H) h(G), что противоречит хроматической эквивалентности Н и G. # Предложение 5.3. Пусть r 2, q 2ut 3. Тогда граф K(q + 2,q+l,...iq + l,q,...,q), где компонента q+І повторяется г — 2 раза, а компонента q повторяется s + 1 раз, является х-определяемым. Доказательство. Пусть G = К(и2), где и2 — атом (2.5). Тогда для Н в силу леммы 4.1 имеем v = {п\,п2,... ,щ) = {q + 1,..., q + 1, q,. q), где компонента +1 повторяется г раз, а компонента q — s = t — г раз. Здесь е = 1 и поэтому & = Сз = 0. Следовательно, & = — (73( і) - з( )) = (6 — 1)(п — (q + 2) — q) = п — 2(g + 1). С другой стороны, i = п — щ — rij для некоторых i, j Є {1,2,... ,t} я г j. Отсюда следует, что щ = Uj = q + 1. Таким образом, удаляемое ребро соединяет две вершины из долей, содержащих по g + 1 элементов. В силу имеющейся симметрии можно считать, что удаляемое ребро соединяет две вершины из 1-й и г-й доли графа K(q + 1,..., q + 1, q,..., q). q+1 q+1 g+1 q+l q q t Q H G 2 r-1 r r+1 t Доли графов H и G с номерами 1 и г будем называть особыми, а содержащиеся в них вершины — особыми вершинами. Как и в доказательстве предложения 5.2, через А обозначим число способов выбора двух различных неособых вершин, которые лежат вместе в какой-нибудь неособой доле. Как и раньше, обозначим через Вч число способов выбора двух вершин по одной из двух различных неособых долей, а через В?, — число способов выбора трех вершин по одной из трех различных неособых долей. Тогда ЩН)-ЩЄ) = (q+l)(q+l)B2 -B2 + 2{q+l)B3 -{q+2)qB2-(q+2)B3-qB3=((q+l)2-l-(q+2)q)B2+(2(q+l)-(q+2)-q)B3 = 0. Таким образом, IA(H) - I4(G) = -2 . Так как q 2, получаем h(H) ф h{G), что противоречит хроматической эквивалентности Н и G. # Осталось заметить, что из предложений 5.2 и 5.3 вытекает Теорема 3. Пусть (пі,п2,... ,щ) — разбиение, являющееся атомом решетки разбиений натурального числа п Hat слагаемых, пі ... щ 2 и 3 t. Тогда полный многодольный граф К(пі,п2, ,щ) хроматически определяем. Отметим, что частный случай теоремы при г = 0 был получен в 1988 г. Giudici R.E. и Lopez М.А. [36] (см. также (8) на стр. 5). Другой частный случай следует из результата Zhao Н.Х. [23] (см. также (12) на стр. 6), но при условии q t + 2.

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

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

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

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

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

Перейдем теперь к точному определению используемых нами понятий и к формулировке цели исследования. В данной работе мы рассматриваем только обыкновенные графы, т. е. графы без петель и кратных ребер. Обозначения и терминологию для графов будем использовать в соответствии с [24]. Пусть G - произвольный (гг, т, /г)-граф, т. е. граф, имеющий п вершин, т ребер и к компонент связности. Раскраской, или t-раскраской графа G называется отображение ф из множества вершин V в множество натуральных чисел {1, 2,..., t} такое, что для любых двух различных смежных вершин и и v графа G выполняется ф{и) ф Ф(У), Т. е. любые две различ ные смежные вершины имеют разный "цвет". Граф называется t-раскрашиваемым, если он обладает t-раскраской и — t-хроматическим, если он -раскрашиваемый, но не является (t — 1)-раскрашиваемым; в этом случае число t называется хроматическим числом графа G и обозначается через x{G).

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

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

Укажем еще два хроматических инварианта для графов (см. [25] или [26]): h(G)=A(G) — число треугольников в графе G; I4(G) = vgU(G)-2M(G), где через vg П (G) мы обозначаем число вершинно порожденных подграфов вида П в графе G, т. е. число бесхордных 4-циклов в G, а через Ш (G) — число полных четырехвершин-ных подграфов К± в графе G.

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

Операды конечных помеченных графов и решетокСеменова Алена Валерьевна

Исследование факториального яруса решетки наследственных классов графовЗамараев, Виктор Андреевич

Разработка микроструктурных моделей сложных кристаллических решеток с целью описания упругих свойств графена и алмазаБеринский, Игорь Ефимович