Мы будем работать с неориентированными графами без петель и кратных рёбер и называть их просто графами. Если разрешены кратные рёбра, мы будем говорить о мультиграфе, но петли всё равно будут запрещены. Как обычно, для вершины v Е V(G) мы будем обозначать через Ng(v) окрестность вершины v, то есть множество вершин, смежных с ней; через A(G) и S(G) мы будем обозначать соответственно максимальную и минимальную степень вершины графа G.
В этой работе мы попытаемся обобщить теорему Брукса, утверждающую, что для любого натурального Д ^ 3 и для любого графа G без подграфов вида Кд+1, имеющего Д(G) < Д, верно x(G) < Д, на f-динамические раскраски — модификацию динамических раскрасок, предложенных Монтгомери.
Определение 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-невырожденная раскраска.
В c-невырожденные раскраски обобщаются до (c,p)-невырожденных раскрасок (в наших терминах — до {(p, ф}-динамических). Там получен следующий аналог теоремы Брукса.
...
Асимптотическая точность оценки
Доказательство теоремы 2. Если k = 6, то мы для каждого Д приве
дём граф ДД;6, у которого Д(Сд,6) = Д и у/(2,6)(Сд,6) = ch/(2,6)(Сд,6) = Д + 1. Это просто граф Кд+1.
Если k = 3, то мы для каждого Д ^ 6 с условием Д = 0 (mod 3)
или Д = 1 (mod 3) приведём граф Дд>3, у которого Д(Дд>3) = Д и Xf(2,3) (^д,з) = chf() (^д,з) = 2Д + 1. Для Д = 2 (mod 3) мы предлагаем взять граф G д,3 = Дд-1>3 (и, поскольку у него Д(Дд,3) = Д — 1 < Д,
можно к нему добавить компоненту связности Кд+1, она не изменит
хроматические числа), у такого графа будет выполнено Xf(23) (Дд,3) = ch/l2,„ (СдЛ) = 2(Д — 1) + 1 = 2Д — 1.
Граф Дд>3 при Д = 0 (mod 3) или Д = 1 (mod 3) мы построим так.
Пусть n = 2Д + 1, тогда n = 1 (mod 6) или n = 3 (mod 6). Согласно, рёбра графа Kn можно разбить на (2д+1)д непересекающихся тре
угольников. Построим двудольный граф Дд,3, в первой доле которого n
вершин, соответствующих вершинам этого Kn, а во второй доле
(2д+1)д
3
вершин, соответствующих треугольникам. Вершину из первой доли бу-
дем соединять с вершиной из второй доли, если соответствующая вершина Kn лежит в соответствующем треугольнике разбиения. Тогда степени вершин первой доли равны Д, а второй доли — трём. Таким образом Д(Од;3) = Л. Осталось заметить, что в любой /(2,з)-динамической раскраске этого графа все n вершин первой доли обязаны быть покрашены в разные цвета, потому что у любой пары вершин есть общий сосед во второй доле, и у этого соседа все три вершины в окрестности должны быть разных цветов. Таким образом, chy(2 6) (Од,6) > Xf(2 6) (Од,6) > 2Л+1. Понять, что chf(26) (Од,6) С 2Л + 1, можно, например, по теореме 1.
