1.1 История вопроса
Пусть G - простой граф степени d > 3, т.е. максимальная степень его вершины A(G) = d. Потребуем еще, чтобы G не содержал Kd+1 - полный подграф (клику) на d +1 вершине. Правильные раскраски G в к цветов, это отображения р: V(G) ^ {1,..., к} такие, что p(u) = p(v), при {u, v} G E(G). Сокращенно будем называть их правильные k-раскраски. Хроматическое число x(G) - минимальное к такое, что существует правильная раскраска G. В данной работе мы будем преимущественно изучать d-раскраски.
Известная теорема Брукса утверждает, что хотя бы одна правильная d-раскраска G существует, иначе говоря y(G) < d. При этом существует множество обобщений этого результата, одним из которых является вообще-то и эта работа. Одно из направлений усилений состоит в уменьшении числа цветов. Статья [1], которая еще будет упомянута, доказывает, что если G не содержит также и Kd, то y(G) < d — 1, для достаточно больших d > 1014. Конкретно u(G) - размер наибольшей клики G ив общем клики большого размера играют важную роль в правильных раскрасках графа, так как являются самыми «труднораскрашиваемыми» множествами. Например, в [5] этот же автор показал: ’’существует е > 0, что x(G) < (1 — s)(A(G) + 1) + sw(G)” и другие похожие вариации. Гипотеза Хайоша и вовсе утверждает, что в некотором смысле, только это и является определяющим фактором: ’’Если y(G) = q, то G содержит подразбиение Kq в качестве подграфа”, что на момент написания этого текста доказано для y(G) = 4 (см. [4] стр 136). Подразбиение графа - замена нескольких ребер на непересекающихся простые пути.
Мы же более подробно остановимся на другой «ветке» результатов: количество цветов остается неизменно d, но на раскраску накладываются дополнительные условия. Наиболее интересным для нас будет исследовать окрестности вершин, а более конкретно, чтобы цвета в них были распределены примерно поровну. Попробуем считать количества цветов в представленных в N(V) по v G V(G). Это является в некотором смысле самым сильно-усложняющим условием к правильности раскраски: последовательно вершину раскрасить тем проще, чем меньше цветов в ее окрестности уже есть.
Для начала в [6] вводится понятие динамической раскраски - такой, что в окрестности любой невисячей вершины представлено не менее двух цветов. Показано, что при d > 8, динамическая раскраска связного G существует тогда и только тогда, когда G не является подразбиением Kd+1. Эта идея развивается на гиперграфы, см. [7]. Наконец, в [3] вводится ключевое для этой работы понятие невырожденной раскраски. Раскраска называется (с,р)-невырожденной если в окрестности любой вершины степени хотя бы p представлено хотя бы c разных цветов. Доказано, что если p > (c3 + 8c2 + 19c + 6)(c +1), то G имеет (c,p)-невырожденную d-раскраску. При p ~ d этот результат дает d4 (1 — o(1)) цветов в окрестности вершины.
Отметим исследование и, в некотором смысле, двойственного условия. В работе [2] исследуется существование «умеренной» (ориг. frugal) раскраски, правда уже в d +1 и более цветов. в-умеренная раскраска не может содержать один цвет в окрестности вершины более чем в в экземплярах. Доказано, что существует правильная в-умеренная раскраска в d +1 цвет для в = log8(d), при d > e10 , и ряд оценок на количество на требуемых цветов при разных в-...
3.1 Пример-органичение сверху
Пусть d - четно. Рассмотрим d копий Kd+1 без одного ребра и одну вершину v, соединенную с концами всех этих антирёбер. Каждая пара вершин из одной клики обязана быть покрашена в один цвет, то есть для v точно mv < d.
3.2 Простые случаи
В графах с обхватом не менее двух или хотя бы без больших клик (w(G~) < d — 2 • 104д/d ln d), правильная перестройка графа не требуется и для них mv ~ dev, так как таково матожидание величины T1.
Аналогичная ситуация с покраской хотя бы d +1 цвет. Любая случайная предраскраска продолжается до правильной и правильная перестройка графа не нужна.
