Тема: О раскрасках графов

Мы будем работать с неориентированными графами без петель и крат­ных рёбер и называть их просто графами. Если разрешены кратные рёб­ра, мы будем говорить о мультиграфе, но петли всё равно будут запре­щены. Как обычно, для вершины v Е V(G) мы будем обозначать через Ng(v) окрестность вершины v, то есть множество вершин, смежных с ней; через A(G) и S(G) мы будем обозначать соответственно максималь­ную и минимальную степень вершины графа G.
В этой работе мы попытаемся обобщить теорему Брукса [1], утвер­ждающую, что для любого натурального Д ^ 3 и для любого графа G без подграфов вида Кд+1, имеющего Д(G) < Д, верно x(G) < Д, на f-динамические раскраски — модификацию динамических раскрасок, предложенных Монтгомери в [2].
Определение 1. Пусть f: No ^ No — частичная функция. Раскраску графа G будем называть f-динамической, если для каждого p Е Dom f верно следующее: у каждой вершины v Е V(G), имеющей степень deg v ^ p, в её окрестности имеются вершины хотя бы f (р) различных цветов.
Через Xf (G) будем обозначать f -хроматическое число графа G, то есть наименьшее натуральное m такое, что G имеет правильную f-динамическую раскраску в m цветов, или правильную f -динамическую m-раскраску (или +гс>, если такого числа m не существует).
Будем говорить, что G списочно f -раскрашиваем в m цветов, если для любого назначения вершинам G списков цветов из некоторой па­литры P существует правильная f-динамическая P-раскраска G, в ко­торой каждая вершина покрашена в некоторый цвет из её списка. Че­рез chf(G) будем обозначать списочное f -хроматическое число графа G, то есть наименьшее натуральное m такое, что G является списочно f-раскрашиваемым в m цветов (или +то, если такого числа m не суще­ствует).
Мы будем через {(p1,c1), (p2,c2),... , (pq, cq)} обозначать частичную функцию, для каждого i отображающую pi в ci. В частности,
• 0-динамическая раскраска — это просто раскраска (соответствую­щее хроматическое и списочное хроматическое число обозначаются X(g) и ch(G));
• {(2, 2)}-динамическая раскраска — это динамическая раскраска гра­фа (соответствующее хроматическое и списочное хроматическое число обозначаются y2(G) и ch2(G));
• {(c, c) }-динамическая раскраска — это c-невырожденная раскрас­ка.
В [4] c-невырожденные раскраски обобщаются до (c,p)-невырожденных раскрасок (в наших терминах — до {(p, ф}-динамических). Там получен следующий аналог теоремы Брукса.
Теорема (Н. В. Гравин, 2009). Пусть G — граф, натуральное Д > 3 таково, что G не содержит подграфа Кд+1 и имеет &(G) С Д. Тогда для любого натурального c ^ 2 выполнено X{(p,c)}(G) С Д, где
p = (с3 + 8c2 + 19c + 6) (c + 1).
Это весьма сильный результат, однако он предлагает большее, чем теорема Брукса, лишь для очень большой палитры (например, при c = 2 условие динамичности накладывается лишь на вершины степеней, не меньших 252, значит, и раскрашивается такой граф не менее чем в 252 цвета). В нескольких работах по динамическим раскраскам были приме­нены более тонкие методы, позволяющие сильно сократить эту границу. Например, в следующих работах доказано существование раскрасок при условии, что число используемых цветов на один больше, чем макси­мальная степень графа.
Теорема (H.-J. Lai, B. Montgomery, H. Poon, 2003, [3]). Пусть G — граф, натуральное Д ^ 3 таково, что &(G) С Д. Если Д = 3, то G не содержит компоненту связности C5. Тогда y2(G) С Д + 1.
Теорема (S. Akbari, M. Ghanbari, S. Jahanbekam, 2009, [5]). Пусть G — граф, натуральное Д ^ 3 таково, что &(G) С Д. Если Д = 3, то G не содержит компоненту связности C5. Тогда ch2 (G) С Д + 1.
В 2010 году в [6] Карпов доказал динамический вариант теоремы Брукса (то есть использовал в динамической раскраске графа Д^) цве­тов), начиная с максимальной степени восемь; в [7] он усилил этот ре­зультат, доказав его же для всех Д ^ 6.
Теорема (Д. В. Карпов, 2016, [7]). Для графа H назовём его 1-подразбиением граф, получаемый из H заменой нескольких (возможно, нуля) рёбер на цепочки длины два (с каждой такой цепочкой добавляется одна новая вершина степени два). Обозначим через Kn класс всех 1-подразбиений графа Kn.
Пусть G — граф, натуральное Д > 6 таково, что Д(С) < Д.
1. Если G имеет компоненту связности из £д+1, то y2(G) = Д + 1.
2. Если G не имеет компоненты связности из £д+1, то y2(G) < Д.
В этой работе мы докажем следующий результат.
Теорема 1. Пусть /(2,k) — частичная функция {(2, 2), (k, 3)}.
Пусть G — граф, натуральное число Д таково, что Д^) < Д, k е {3, 4, 5,6}. Обозначим g(k) = {(3, 6), (4,13), (5, 31)}. Тогда:
• при k е {3, 4, 5} и Д > g(k) выполнено chy(2fc) (G) < |~| Д + 1;
• при k = 6, а также при k е {3,4,5} и Д < g(k) выполнено chf(2,k) (G) < max{3k + 1, Д + 7 + Ге(Д, k)]}.
Функция е(Д, k) = 0(имеет вид
24k - 84
Д + 13 - 2k + V4k2 + Д2 + 1 - 4ЕД - 4k + 26Д ’
В частности, при k = 6 выполнена оценка
60
' ' < ma^19,Д + 7+ Д + 1 + 7(Д + 1)2 + 120 [
и верно chf(2 6) (G) < Д + 8 при Д > 28.
Следствие 1. Пусть G — граф, натуральное число Д > 28 таково, что Д^) < Д. Тогда chf(2 6)(G) < Д + 8.
Следствие 2. Пусть G — граф, натуральное число Д таково, что Д^) < Д. Тогда верны следующие неравенства:
• chf(2,3) (G) < 2Д + 1 при Д > 6;
• chf(2,4) (G) < |"|A"| + 1 при A > 13;
• chf(2 5) (G) < I"6 A"| + 1 при A > 31;
При k E {3, 6} мы докажем, что этот результат асимптотически точен по A (и отличается от точного на некоторую константу).
Теорема 2. Пусть k E {3, 6}. Тогда существует бесконечная серия гра­фов G^,k, параметризованная натуральным числом A, что A(G^,k) =
A и Xf(2,k) (G^,k) = Chf(2,k) (G^,k) = 6 A + ©Д^+^(1).
Купить

Цель, которая была достигнута при выполнении работы, заключалась в обобщении теоремы Брукса. Исследования осуществлялись с использованием неориентированных графов без петель и крат­ных рёбер.
Купить