1 Введение 1
1.1 История вопроса 1
1.2 Постановка задачи 2
2 Доказательство основного результата 2
2.1 Перестройка графа 2
2.1.1 Общие понятия и мотивация 2
2.1.2 Конструирование правильной перестройки 3
2.2 Случайная раскраска 5
2.2.1 Определение случайной раскраски 5
2.2.2 Общие рассуждения 6
2.2.3 Вычисления вероятностей некоторых событий 7
2.3 Детерминированная докраска 11
2.3.1 Достижение невырожденности 11
2.3.2 Хорошие вершины 11
2.3.3 Плохие вершины 12
2.3.4 Подведение итогов 15
3 Связанные замечания 17
3.1 Пример-органичение сверху 17
3.2 Простые случаи 17
Список литературы 20
Купить

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 , и ряд оценок на количество на требуемых цветов при разных в-
1.2 Постановка задачи
Перейдем к основным определениям и понятиям этой работы. N(v) - окрестность вершины v G V(G), а степень v обозначим более сокращенно dv = deg(v) = |N(v)|. Пусть X С V(G) произвольное множество вершин и р - правильная d-раскраска. Рассмотрим величину, зависящую от раскраски mX (р) - количество разных цветов представленных в X, а mX G R некоторая нижняя граница для mX (р) которую рас­краска должна стараться выполнить. Обозначим для v G V(G): mv(р) = mN(v) (р) и mv = mN(v). Рассмотрим произвольный набор чисел {mv}veV(G) •
Определение. Правильная раскраска р называется mv-невырожденной, если mv (р) > mv для всех v G V(G).
Теорема 1. G - простой граф степени d не содержащий Kd+1, а d - достаточно велико. Пусть mv = dg — 1Щ/dv ln d для каждой вершины v. Тогда существует mv- невырожденная d-раскраска графа G.
Замечание. Результат [3] в этих терминах для больших d дает mv-невырожденную раскраску с mv ~ d 1. Текущий же дает mv ~ cd, 0 < c < 1, то есть линейную оценку, что является асимптотически неулучшаемым результатом. Естественно, можно пы­таться добиться большей константы c чем 1-8. В графах с u(G) < d — 2 • 104VdIn d она достигает e-2, но простой пример показывает что больше чем 2 получить не удастся.
Купить