Содержание к диссертации
Введение
1. Ориентированные раскраски 16
1.1. Обзор и обсуждение результатов главы 16
1.2. Связь с круговыми раскрасками и алгебраическими потоками 21
1.3. Доказательство теоремы 1.1 23
1.3.1. Свойства гомоморфизмов в С(5; 1,2) 23
1.3.2. Основные структурные свойства минимального контрпримера 25
1.3.3. Завершение доказательства теоремы 28
1.4. Доказательство теоремы 1.2 34
1.4.1. Структурные свойства минимального контрпримера 35
1.4.2. Завершение доказательства теоремы 39
1.5. Доказательство теоремы 1.3 40
1.5.1. Свойства гомоморфизмов в Р(47) 40
1.5.2. Структурные свойства минимального контрпримера 42
1.5.3. Завершение доказательства теоремы 47
2. 2-дистанционная раскраска 50
2.1. Обзор и обсуждение результатов главы 50
2.2. Доказательство теоремы 2.1 51
2.2.1. Случай Д() = 3 51
2.2.2. Случай д 8 57
2.3. Доказательство теоремы 2.2 63
2.3.1. Структурные свойства минимального контрпримера 64
2.3.2. Завершение доказательства теоремы 70
Литература 75
- Связь с круговыми раскрасками и алгебраическими потоками
- Основные структурные свойства минимального контрпримера
- Структурные свойства минимального контрпримера
- Структурные свойства минимального контрпримера
Введение к работе
1. Общая характеристика работы
Раскраска графа в широком смысле есть разбиение дискретного объекта на более простые подобъекты. Ввиду своей общности теория раскраски занимает в дискретной математике центральное положение и имеет многочисленные приложения, особенно в информатике (распределение памяти, диагностика ошибок в программах и т. д.), задаче назначения частот в мобильном телефонировании, в теории расписаний и др. Гомоморфизмы графов - более общее понятие, чем раскраска (действительно, задача классической вершинной раскраски есть не что иное, как гомоморфизм на полный граф), и в последнее время они интенсивно изучаются в самых разных аспектах.
Раскраска плоских графов также представляет собой широкую область исследования, выросшую из знаменитой проблемы четырех красок, решенной в 197G г. К. Аппелем и В. Хакеном [2, 3, 4], и в которой в настоящее время работают сотни специалистов.
Доказательство теоремы о четырех красках основано на построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другой пример того же рода — это построенная О.В. Бородиным [46, 5] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную ракскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, — ациклический). Теорема О.В.Бородина об ациклической 5-раскраске включена во введении книги В.Тофта и Т. Йенсена [22] в число 40 важнейших результатов по раскраске графов за все годы. В последнее время в работах зарубежных математиков эта теорема получила ряд приложений к другим задачам раскраски. В главе "Плоские графы"этой книги цитируются более 20 результатов О.В. Бородина, А.В. Косточки, В.А.Аксенова и Л.С.Мельникова. Коллектив лаборатории теории графов Института математики СО РАН является одним из мировых лидеров именно в области раскраски плоских графов.
В диссертации изучаются ориентированная и 2-дистанционная раскраски разреженных плоских графов. В теории графов мерой разреженности графа G принято считать максимальную среднюю степень вершин, mad(G), всех его подграфов. Для плоских же графов разреженность обычно выражают в терминах обхвата g(G), т. е. длины минимального цикла. Нетрудно показать, что если граф G плоский, то mad(G) < 3 _2. С другой стороны, в силу известной теоремы Эрдеша [14] о раскраске случайных графов, существует (неплоский) граф G, имеющий произвольно
большие g(G) и mad{G). Часть результатов диссертации доказывается для произвольных разреженных графов, т. е. с использованием максимальной средней степени, а не обхвата.
Рассматриваемые в диссертации виды раскрасок занимают в теории графов заметное место. Первый из них исследуется с конца 70-х годов, а второй — с начала 90-х. Оба вида раскрасок привлекают интерес специалистов по теории графов как своей математической красотой, так и связями с другими видами раскрасок (ациклической, круговой, тотальной, реберной, (р, д)-раскраской и предписанной) и алгебраической теорией потоков.
Ориентированные раскраски сводятся к построению гомоморфизма широких классов ориентированных графов на специально подобранные орграфы (мишени) с небольшим числом вершин. Отметим, что классическая задача вершинной раскраски может рассматриваться как построение гомоморфизма заданного графа на наименьший полный граф Кп. Ориентированная раскраска иногда оказывается тесно связанной с другой задачей о гомоморфизме, круговой раскраской, в которой ищется гомоморфизм неориентированных графов на минимальный циркулянт. Другими словами, требуется раскрасить вершины заданного графа числами 0,1,..., к — 1 так, чтобы цвета любых соседних вершин отличались на величину, ограниченную как снизу, так и сверху. Отметим, что в классической раскраске вершин ограничение сверху на расстояние между цветами соседних вершин отсутствует, а снизу равно 1, в то время как в (р, 0)-раскраске ограничение снизу равно р, а ограничение сверху также отсутствует.
За пределами теории графов интерес к 2-дистанционной раскраске объясняется тем, что и она сама и такие ее обобщения как (р, д)-раскраска и предписанная (р, q, т. к. частоты ближе расположенных источников должны различаться сильнее ввиду интерференции волн. Понятно, что (1,1)-раскраска есть в точности 2-дистанционная раскраска. При этом иногда каждый источник имеет свой собственный набор разрешенных частот, т. е. возникает известная в теории графов задача предписанной раскраски.
Цель диссертационной работы состоит в получении новых результатов о раскрасках (ориентированных и 2-дистанционных) разреженных графов, в основном плоских, а также вспомогательных результатов о строении таких графов.
Работа носит теоретический характер; полученные результаты о 2-дистанцион-ных раскрасках плоских графов имеют отношение к задачам, возникающим в мо-
бильной связи, в том числе к задаче о назначении радиочастот. В диссертации получены следующие основные результаты:
Установлено структурное свойство минимальных графов, не допускающих гомоморфизмов на С(5; 1,2) и цикл С5 (отсутствие так называемых "мягких" циклов), из которого, в частности вытекает, что любой плоский граф обхвата не менее 12 имеет ориентированную 5-раскраску.
Доказана ориентированная 7-раскрашиваемость плоских графов обхвата не менее 7.
Получена структурная теорема для плоских графов без треугольников, из которой вытекает, что такие графы можно гомоморфно отобразить на турнир Пэли порядка 47.
Получены достаточные условия (в терминах максимальной степепи Д((?) и обхвата g(G)), при которых 2-дистанционное хроматическое число X2(G) графа G достигает своей нижней границы A(G) + 1. В частности, это имеет место при: (а) Д((?) = 3 и g(G) Z 24; (б) g(G) > 8 и A(G) ^ 15.
Ввиду того, что существуют плоские графы с g(G) ^ б, для которых Xi{G) > Д((7) + 1 при произвольно большом Д(С?), при д = 6 для выполнения равенства X2{G) = Д(<2) +1 были найдены дополнительные ограничения на структуру графа. А именно, это равенство имеет место, если Д ^ 179, а каждое ребро инцидентно 2-вершине (последнее условие выполняется, в частности, для тотальных графов).
Среди всех результатов диссертации выделим в качестве важнейших первый и третий; оба они касаются ориентированных раскрасок, обсуждаются в разделе 3 введения и подробно излагаются в главе 1.
Заметим, что некоторые из результатов диссертации могли бы быть обобщены на достаточно разреженные не обязательно плоские графы. Реально лишь первый результат доказан нами в более общем виде — в терминах mad(G).
Результаты диссертации получены с помощью метода сводимых конфигураций, т. е. путем построения неизбежных систем конфигураций, сводимых в заданной задаче раскраски. Для одной из задач потребовалось установить ряд новых свойств турнира Пэли Р(47), что было сделано с использованием компьютера.
Всего по теме диссертации автором опубликовано 9 журнальных статей [56, 49, 51,50, 55, 57, 52, 53, 54] и одна статья [58] в трудах конференции. Все вышеперечисленные основные результаты диссертации опубликованы. Некоторые из полученных диссертантом результатов не были включены в диссертацию.
Диссертация состоит из введения, двух глав и списка литературы, содержащего 58 наименований.
Все доказательства, изложенные в диссертации, подробно разбирались на семинаре "Теория графов" Института математики СО РАН в 2004-2006 гг.. Работа автора
по теме диссертации в 2005-2006 гг. поддержана двумя грантами РФФИ, а в 2006 — грантом ректора Якутского государственного университета имени М.К. Аммосова. Доклад с обзором результатов диссертации был сделан на научной конференции 10-х Лаврентьевских чтений, посвященных 50-летию Якутского госуниверситета (2006), и получил первую премию на секции "Математика, механика и физика".
Диссертант благодарит всех сотрудников лаборатории теории графов Института математики СО РАН и особенно своего научного руководителя О.В. Бородина за поддержку и неоценимую помощь, оказанные при подготовке диссертации, а также А.Н. Глебова за внимательное прочтение и сделанные замечания по большинству из опубликованных статей.
2. Основные понятия и обозначения
В работе рассматриваются конечные графы без петель и кратных ребер, как неориентированные так и ориентированные. Цель этого раздела — дать определения наиболее часто встречающимся в тексте понятиям и обозначениям. Локальные понятия и обозначения будут даваться по ходу дела в соответствующем контексте.
Через V(G) = V и E(G) = Е соответственно обозначаются множества вершин и ребер графа G = G(V,E). Через е = uv обозначается любое ребро с концами в вершинах и и v, при этом вершины и и v называются смежными между собой и инцидентными ребру е. Ребра uv и uw называются смежными. Через d(v) = dc(v) обозначается степень вершины v Є V(G) в G, т. е. число инцидентных вершине v ребер из E(G) (петли засчитываются дважды). Любая вершина степени d называется d-вершиной. Используются обозначения 6(G) и A(G) соответственно для минимальной и максимальной степеней вершин в G. Граф G называется пустым, если E(G) = 0, и полным, Кп, если любые две из его п вершин смежны.
Если X С V(G) — произвольное подмножество вершин графа G, то через G[X] обозначается подграф в G, порожденный подмножеством X, т. е. подграф с множеством вершин X, содержащий все те ребра из E(G), концы которых принадлежат X. При этом если \Х\ ^ 2, то окружением N(X) = Nq(X) подмножества X в G называется множество всех вершин из V(G), смежных с вершинами из X. Окружением N(v) вершины v (случай |Х| = 1) называется множество, состоящее из всех вершин из V(G), смежных с вершиной v, и всех ребер из E(G), инцидентных вершине v. Подмножество вершин X называется независимым в G, если подграф G[X] — пустой.
Пусть W С V(G)uE(G) — произвольное подмножество вершин и ребер графа G (или подграф в G, рассматриваемый как множество из вершин и ребер). Тогда через G — W обозначается подграф в G, получаемый удалением из G всех ребер е eW и всех вершин v W вместе с инцидентными им ребрами.
Через Р = V\V2... vn обозначается цепь с вершинами Vi,v2,...,vnu ребрами viv2, ^2) іvn-\Vn, а через С = [v\,v2,...,vn) — цикл с вершинами vx,v2,...,vn и ребрами Viv2, v2v3, ... ,u„_iun, ип«і. Длиной цепи Р (цикла С) называется число п — 1 (соответственно п), т. е. число ребер при прохождении этой цепи (цикла). Цепь Р (цикл С) называется простой (простым), earn все вершины Vi,v2,...,vn различны. Под u-v-цепъю понимается любая простая цепь с концами в вершинах и и v. Множество вершин цепи Р (цикла С) также обозначается через Р (соответственно С), если исключены какие-либо недоразумения. Под п-циклом понимается любой простой цикл длины п. Простой цикл длины 3,4,... называется также треугольником, четырехугольником и т. д. Подграф в G с множеством вершин {u,v\,...,Vk] и множеством ребер {uvi,...,uvk} называется k-звездой при вершине и, определяемой вершинами г/і,..., г»*. Далее под к-цепью будем понимать цепь, состоящую из в точности к вершин степени 2, а под (k\,..., кд)-вершиной понимается d-вершина, инцидентная d различным цепям, где г'-я цепь (1 ^ г < d) содержит не менее к{ вершин степени 2.
Через d(u, v) обозначается расстояние между вершинами и и г/ в графе G, т. е. длина кратчайшей u-v-цеті в G (при этом d(u,v) = со, если вершины и и v принадлежат различным компонентам связности в G). Граф G называется к-связнъш, если G связен и удаление из G любых менее чем к вершин приводит к связному графу. Вершина v Є V(G) называется точкой сочленения графа G, если граф G — v несвязен.
Через g(G) обозначается обхват графа G, определяемый как длина кратчайшего простого цикла в G. Под разреженностью плоского графа понимается его обхват, а для не обязательно плоского графа G — максимальная степень mad(G) его подграфов. Поскольку любой подграф плоского графа G плоский, то нетрудно показать, что mad(G) < ,9Х]2. Таким образом, разреженный плоский граф является разреженным и как абстрактный граф. Нередко результаты для разреженных плоских графов допускают обобщения на произвольные разреженные графы. Например, теорема 1.1 о том, что плоский граф с обхватом не менее 12 ориентированно 5-раскрашиваем, фактически доказана нами в более общем виде: если произвольный граф G обхвата не менее 5 имеет mad(G) < у, то G ориентированно 5-раскрашиваем.
Квадратом G2 графа G называется граф с множеством вершин V(G), в котором вершины и и v смежны тогда и только тогда, когда dc(u,v) ^ 2. Под 2-дистащионной степенью d2(v) вершины v графа G понимается ее обычная степень dG2(v) в графе G2, т. е. число вершин графа G, находящихся на расстоянии не более 2 от вершины v в G. Используется обозначение 62(G) для минимальной 2-дистанционной степени вершин в G (которая равна S(G2)).
Раскраской вершин графа G называется приписывание его вершинам некоторых
цветов, т. е. отображение ip : V(G) -> С, где С есть множество цветов. Раскраска вершин графа называется правильной, если любые две смежные вершины окрашены в различные цвета. Наименьшее число цветов в правильных раскрасках графа G называется его хроматическим числом и обозначается через x(G)- При этом если x{G) ^ к, то граф G называется к-раскрашиваемым, а если х(@) = к, то G называется к-хроматическим.
Говорят, что на множестве вершин графа G задано предписание L размера к, если определены множество цветов С и отображение L : V(G) -> 2е такие, что \L(v)\ = к при каждом v Є V(G). Граф G называется предписание к-раскрашиваемым, если для любого множества С (где \С\ ^ к) и любого предписания L : V(G) —У 2е размера к существует такая правильная раскраска ip : V(G) —> С, что ^>(и) Є L(u) при каждом w Є V(G) (т. е. цвет каждой вершины принадлежит ее предписанию). Наименьшее целое число к такое, что граф G является предписаний ^-раскрашиваемым, называется его списочным хроматическим числом и обозначается через Xі {G).
Правильная раскраска вершин графа называется ациклической, если подграф, порожденный вершинами любых двух цветов, является ациклическим. Если р и q — целые неотрицательные числа, то (p,q)-раскраской вершин графа G в к цветов называется такое отображение ip : V(G) -> {1,2,...,к}, что \<р(и) — (p(v)\ ^ р при d(u,v) = 1 и |(/?(и) — ip(v)\ ^ q при d(u,v) = 2. Наименьшее натуральное число к такое, что существует {р, д)-раскраска вершин G в к цветов, называется (p,q)-хроматическим числом графа G и обозначается через Xp,q(G)- При этом любая (1,1)-раскраска графа G называется его 2-дистанционной раскраской, а соответствующее хроматическое число Xi.i(^) ~ 2-дистанционным хроматическим числом графа G, которое обозначается как X2{G). Эквивалентное определение 2-дистанционной раскраски состоит в том, что любые две вершины, находящиеся в графе G на расстоянии не более 2, окрашены в различные цвета. Следовательно, понятие 2-дистанционной раскраски графа G равносильно понятию правильной раскраски графа G2, а 2-дистанционное хроматическое число X2(G) совпадает с обычным хроматическим числом x{G2)- Так же, как и в случае с правильной раскраской (при С = Z), определяются понятия предписанной (р, q)-pacKpacKU и предписанной 2-дистанционной раскраски графа G и соответствующие списочные хроматические числа, которые
обозначаются как x\d@) и xil^) (ПРИ этом Х?№) = Xі{G2))-
Гомоморфизм графа G в граф Н есть отображение <р из V(G) в V(H), которое сохраняет ребра (или дуги), т. е. ху E(G) => (р(х)ір(у) Є Е(Н).
Гомоморфизмы графов изучались в литературе как обобщение раскраски графов. Заметим, что неориентированный граф G имеет А;-раскраску если и только если G имеет гомоморфизм в полный граф Кк- Поэтому хроматическое число неориентированного графа G можно эквивалентно определить как минимальное число вершин
в неориентированном графе Я таком, что G имеет гомоморфизм в Н.
В дальнейшем рассматриваются орграфы без параллельных дуг. Ориентированная к-раскраска орграфа G есть (ориентированный) гомоморфизм в ^-вершинный орграф Н. Ориентированное хроматическое число o(G) графа G определяется как минимальное к, при котором каждая ориентация графа G имеет ориентированную А-раскраску. Заметим, что ориентированное хроматическое число графа может существенно отличаться от его хроматического числа. Например, существуют двудольные графы с произвольно большим ориентированным хроматическим числом.
Плоским графом называется граф, вершинами которого служат точки на плоскости, а ребрами — жордановы кривые, соединяющие пары вершин так, что различные кривые пересекаются только в своих общих концевых вершинах. Граф G называется планарным, если он изоморфен какому-либо плоскому графу. Гранями плоского графа G называются области, на которые плоскость разбивается его ребрами и вершинами. Единственная бесконечная область, образующаяся при таком разбиении, называется бесконечной или внешней гранью. Через F(G) = F обозначается множество всех граней плоского графа G = G(V, E,F).
Если плоский граф G связен, то каждая его грань / є F(G) ограничена некоторым (не обязательно простым) циклом, который называется граничным циклом грани /. Ранг грани / определяется как длина ее граничного цикла и обозначается через г(/). Любая грань ранга г называется r-гранъю. Если грань / ограничена простым циклом С/ = (vi,V2,...,vr), то запись (vi,V2,...,vr) используется для обозначения как цикла С/, так и самой грани / (если исключены какие-либо недоразумения). Говорят, что вершина v Є V(G) (ребро є Є E{G)) инцидентна {инцидентно) грани / 6 F(G), если v (соответственно е) принадлежит граничному циклу грани /. Две грани, инцидентные одному и тому же ребру, называются смежными.
Плоский граф G называется плоской нормальной картой, если d(v) ^ 3 и г(/) ^ 3 для любых v Є V(G) и / б F(G). Нетрудно доказать, что плоский граф двусвязен тогда и только тогда, когда каждая его грань ограничена простым циклом. Штей-ницем [38] было доказано, что 3-связные плоские графы взаимно-однозначно соответствуют эйлеровым многогранникам (ограниченным выпуклым многогранникам в Л3). Поэтому в настоящей работе понятия эйлерова многогранника и 3-связного плоского графа не различаются.
Для любого плоского графа G(V, Е, F) справедлива формула Эйлера
\V\-\E\ + \F\ = 2, (1)
которая для плоского графа G с обхватом g(G) может быть переписана в виде
(Щ^2\Е\ - g(G)\V\j + (2\Е\ - g(G)\F\) =
= Е(^И^) -9{G)) + ('(/)--*9(G)- (2)
Откуда следует, что средняя степень его вершин не превосходит Д_'2. В частности, при g(G) — 4 формула (2) приобретает симметричный вид:
(<^)-4) + Х>(/)-4) = -8. (3)
vCV feF
Второе равенство в (2) можно кратко записать в виде
ф) = -2g(G), (4)
xeVUF
где величины
li{v) = ^fld{v)-g{G) и р(/) = г(/) -g(G) (5)
называются первоначальным зарядом вершины v 6 V"((j) и первоначальным зарядом грани / Є ^(G) соответственно.
Отметим, что если формула (2) применяется к плоскому графу G с обхватом g{G), то первоначальные заряды граней, определяемые равенствами (5), неотрицательны. Поэтому из формулы (2) следует, что
>(г,К-25(G). (6)
Используемый в работе общий метод перераспределения эйлеровых вкладов (зарядов) заключается в том, что допускается существование контрпримера G к доказываемому утверждению о строении плоского графа G. Для этого графа рассматривается формула Эйлера в виде (2). При этом заряды элементов в G определяются формулами (5). Вводятся правила перераспределения зарядов между элементами из G, в соответствии с которыми первоначальные заряды /j,(x) преобразуются в окончательные заряды ц*(х) так, что сумма всех зарядов в G остается неизменной, т. е. отрицательной. Далее с использованием структурных свойств контрпримера G доказывается, что каждый из окончательных зарядов вершин и граней графа G неотрицателен. Полученное противоречие опровергает предположение о существовании контрпримера G.
3. Обзор результатов диссертации
При доказательстве всех результатов диссертации используется метод сводимых конфигураций, состоящий в следующем. Для заданной задачи раскраски строится
система структурных фрагментов, которые не могут содержаться в минимальном контрпримере к доказываемому утверждению. (Такие фрагменты называются сводимыми конфигурациями.) Эта система должна обладать свойством неизбеоюности, смысл которого в том, что каждый граф рассматриваемого класса содержит хотя бы одну из конфигураций данной системы. Неизбежность доказывается с помощью описанного выше метода перераспределения эйлеровых вкладов. Доказательство сводимости конкретной конфигурации состоит в удалении ее из графа, раскраске получившегося меньшего графа и последующем продолжении получившейся раскраски на весь граф. Можно сказать, что решить задачу раскраски методом сводимых конфигураций - это то же самое, что построить неизбежную систему сводимых конфигураций для данной задачи.
В сущности метод перераспределения эйлеровых вкладов служит для доказательства неизбежности системы конфигураций. Иногда неизбежная система конфигураций возникает не в связи с решением задачи раскраски, а служит описанием строения некоторого класса графов, например, плоских. В этом случае конфигурации должны быть простыми, естественными, т. е. "красивыми". Иногда такая структурная теорема дает лишь основу для построения неизбежной системы сводимых конфигураций для поставленной задачи раскраски, а в редких случаях дает для нее уже готовую систему сводимых конфигураций.
В главе 1 содержатся результаты об ориентированных и круговых раскрасках разреженных графов (не обязательно плоских). Среди всех результатов диссертации наиболее важными мы считаем теоремы 1.1 и 1.3.
Ориентированная fc-раскраска орграфа G есть ориентированный гомоморфизм из G в некоторый А;-вершинный турнир Н (мишень), т. е. отображение ц> из V(G) в V(H), при котором ху Є E(G) => ір(х)<р(у) Є Е{Н). Другими словами, вершины орграфа Я считаются цветами и требуется каждой вершине из G приписать цвет так, чтобы любая дуга в G, начало которой окрашено в цвет г, а конец — в j, имелась бы в мишени Н.
Ориентированное хроматическое число o(G) определяется как минимальное к, при котором G имеет ориентированную ^-раскраску. Ориентированное хроматическое число графа может сильно отличаться от его хроматического числа. Например, существуют двудольные графы с произвольно большим ориентированным хроматическим числом (достаточно заменить каждое ребро графа Кп на путь длины 2, и тогда концы каждого такого пути в полученном графе К„, т. е. все вершины исходного графа Кп, обязаны краситься в разные цвета, т. к. в мишени нет антипараллельных ДУг).
Б. Курсель [И] доказал, что o(G) ^ З63 для любого плоского графа G, а в [33] этот результат был улучшен до 80 (с использованием ациклической 5-раскрашиваемости
плоских графов, доказанной О.В. Бородиным в [5]). В [10] была доказана следующая теорема, усиливающая результаты работы [31].
Теорема. Пусть G — плоский орграф обхвата д. Тоща (і) если g(G) ^ 14, то o{G) ^ 5, (ii) если g{G) > 8, то o{G) ^ 7, (Ш) если g(G) ^ б, то o(G) < 11, (iv) если g(G) ^ 5, то o{G) ^ 19.
В [7] ограничение в пункте (і) этой теоремы было ослаблено с 14 до 13. Наибольшее значение среди результатов главы 1 имеет доказанная в разделе 1.2
Теорема 1.1. Если орграф G плоский и g(G) ^ 12, то o(G) ^ 5.
Эта задача была поставлена О.В.Бородиным и А.В.Косточкой около 10 лет назад. При доказательстве данной теоремы решающую роль сыграла новая идея глобального перераспределения эйлеровых вкладов, не встречавшаяся до сих пор в работах по плоским графам. (Хотя она теоретически ничему не противоречит, реализовать ее ранее не удавалось.) Ключевой в доказательстве является лемма о "мягком цикле", налагающая строгие ограничения на структуру минимального контрпримера. Эта лемма справедлива для графов произвольного обхвата, поэтому будет полезна в дальнейших исследованиях по ориентированным и круговым 5-раскраскам, связанным с гипотезами Татта [40] и Жеже [21] об алгебраических 5-потоках. В [33] построен плоский граф Go с o{Gq) > 4 и произвольно большим обхватом, поэтому наиболее важными представляются достаточные условия для ориентированной раскрашиваемое именно в 5 цветов.
Отметим, что в нашей работе [52] теорема 1.1 доказывается в более общем виде, а именно, мы доказываем, что любая ориентация графа (не обязательно плоского) с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.
Здесь же укажем на связь между задачами ориентированной и круговой раскрасок. Последняя была введена Венсом в [43] (обзор результатов по круговым раскраскам см. в [7, 45]). Для простоты приведем определение круговой раскраски неориентированного графа G в 5 цветов: требуется раскрасить его вершины цветами 0,1,..., 4 так, чтобы цвета любых двух смежных вершин отличались на 2 или 3 по mod 5, что эквивалентно существованию гомоморфизма графа G на цикл С$. Вопрос о круговой 5-раскрашиваемости плоских графов обхвата 12 также оставался открытым в течение нескольких лет. Нам удалось сначала доказать этот факт, а затем уже теорему 1.1. Оба доказательства имеют одинаковую структуру, но при до-
казательстве теоремы 1.1 пришлось преодолевать дополнительные трудности. Этот результат о круговой 5-раскрашиваемости остался неопубликованным, и его доказательство в диссертацию не включено. Возможно, не возникни вопрос о круговой 5-раскрашиваемости, то и теорема 1.1 не была бы доказана до сих пор, несмотря на усилия ряда исследователей из Франции, США, Чехии и других стран.
Другим усилением вышеупомянутой теоремы из [10] является доказанная в разделе 1.3
Теорема 1.2. Если орграф G плоский и g(G) ^ 7, то o(G) ^ 7.
С другой стороны, для плоских графов без треугольников, т. е. с обхватом не менее 4, в [10] не было получено никакой верхней оценки для ориентированного хроматического числа, лучшей, чем упоминавшаяся в разделе 1.1 введения общая оценка 80, верная для любого плоского графа и вытекающая из ациклической 5-раскрашиваемости плоских графов, доказанной О.В. Бородиным в 1976 г. ([46, 5]). П.Ошам [32] доказал, что плоские графы без треугольников имеют ориентированную 59-раскраску. Отметим, что средняя степень вершин в таких графах может быть сколь угодно близка к 4, как и в упоминавшихся выше графах К*, по при этом о(К^) растет неограниченно с ростом п. Последний из основных результатов главы 1 содержится в разделе 1.4 и состоит в улучшении оценки П. Ошама до 47.
Теорема 1.3. Если орграф G плоский и g(G) ^ 4, то o(G) ^ 47.
Фактически мы доказываем, что каждая ориентация плоского графа с обхватом не менее 4 имеет ориентированный гомоморфизм в турнир Пэли Р(47), т. е. турнир на вершинах 0,1,..., 46, в котором пара ij является дугой из і в j, если и только если j = (i+qk) mod 47, где qk — один из 23 квадратичных вычетов по mod 47. Доказательство использует ряд новых свойств турнира Р(47), найденных нами с помощью компьютера и вызвавших интерес у специалистов по алгебраической комбинаторике. Кроме того, при доказательстве теоремы 1.3 было установлено новое структурное свойство плоских графов, которое интересно само по себе, безотносительно его связи с раскрасками, и может рассматриваться как вклад в структурную теорию плоских графов.
Во второй главе получены достаточные условия (в терминах максимальной степе-пи А (С?) и обхвата g{G)), при которых 2-дистанционное хроматическое число Xi{G) графа G достигает своей нижней границы Д(
Раскраска / : V(G) ч- {l,2,...,k} графа G = (V,Е) называется 2-дистанционной, если любые две вершины на расстоянии не более 2 окрашены в разные цвета. Наименьшее число цветов в 2-дистанционных раскрасках графа G называется 2-дистанционным хроматическим числом графа G и обозначается через X2{G). Задача 2-дистанционной раскраски возникает в приложениях; в частности, она является одной из основных моделей в проблеме распределения радиочастот (ПРР) в сетях
мобильного телефонирования.
В самой теории графов известна старая (1977) гипотеза Г. Вегнера [44] о том, что Xi(G) ^ LfAJ + 1 любого плоского графа G с максимальной степенью Д (см. также монографию Т.Р. Йенсена и В.Тофта [22, п. 2.18]). Пример плоского муль-тиграфа, построенного К. Шенноном [37] (так называемый треугольник Шеннона), показывает, что если верхняя оценка в гипотезе Вегнера верна, то она достижима при Д ^ 8.
Я. ван ден Хойвелом и С. Мак Гиннессом [42] было доказано, что Хг(С) ^ 2Д + 25 для любого плоского графа G с максимальной степенью Д. Независимо Г. Агнарсоном и М.М. Холдорсоном [1] было установлено, что хг{@) ^ [f^J +2 при Д ^ 749. Наилучшей из опубликованных верхних оценок для произвольных плоских графов является Xi{G) ^ [|^1 + 1 "Ри Д ^ 47 ([48]).
Очевидно, что Хг{С) ^ Д+1 для любого графа G (ввиду того, что в любом графе есть звезда .Кід). Возникает вопрос: для каких графов 2-дистанционное хроматическое число равно этой тривиальной нижней оценке? К-таким графам относятся, например, все деревья.
Легко видеть, что при Д = 2 существуют графы с Хг = 4 и произвольно большим обхватом, например, Сзк+і- В [56, 49] нами показано, что при A(G) ^ 3, если плоский граф G разрежен, т. е. его обхват (длина минимального цикла) g(G) ^ 7 при фиксированном Д достаточно велик, то Хг№) = Д + 1.
В диссертацию включены доказательства только тех результатов из работ [56], [49], которые принадлежат диссертанту. Основным результатом раздела 2.1 является
Теорема 2.1. Пусть G — платрпый граф, тогда %г(С) = Д + 1 в каждом из следующих случаев:
(г)Д = Зи<7^24;
(и) Д ^ 15 и g ^ 8.
С другой стороны, как показано в [49], существуют графы с g ^ б, для которых Х2 > Д + 1 при произвольно большом Д. Тем самым в [49] полностью решен вопрос о том для сколь малых g можно гарантировать равенство ^2 = Д + 1 лишь путем наложения ограничения на Д.
При g = 6, ввиду сказанного выше, для выполнения равенства Х2 — А +1 требуются дополнительные ограничения на структуру графа. Вторым основным результатом второй главы является доказанная в разделе 2.3
Теорема 2.2. Если G — плоский граф обхвата 6, в котором Д ^ 179, а каждое ребро инцидентно 2-вершине, то X2(G) = Д +1.
В связи с теоремой 2.2 отметим, что известная задача тотальной раскраски графа G (т. е. совместной раскраски его вершин и ребер, при которой любые два смежных или инцидентных элемента получают разные цвета) сводится к задаче
2-дистанционной раскраски вспомогательного графа G*, в котором каждое ребро инцидентно 2-вершине; а именно, получаемого из G заменой каждого ребра на цепь длины 2.
Как упоминалось выше, 2-дистанционная раскраска есть частный случай (р, q)-раскраски, когда р = q = 1. В работах [53], [55] нами получен ряд обобщений результатов главы 2 на случаи (р, q)- и предписанной (р, д)-раскрасок, связанных с проблемой распределения частот в сетях мобильной связи, но они не включены в диссертацию.
Связь с круговыми раскрасками и алгебраическими потоками
Напомним, что гомоморфизм из графа G в граф Я есть отображение ip из V(G) в V(H), которое сохраняет ребра (или дуги), т. е. ху E(G) =Ф- р(х)(р(у) Е(Н). Иначе говоря вершины орграфа Я считаются цветами и требуется каждой вершине из G приписать цвет так, чтобы любая дуга в G, начало которой окрашено в цвет і, а конец — в j, имелась бы в мишени Я.
Гомоморфизмы графов изучались в литературе как обобщение раскраски графов [18, 17, 20, 22, 27, 31, 30, 33, 36]. Заметим, что неориентированный граф G имеет к-раскраску, если и только если G имеет гомоморфизм в полный граф Кк. Поэтому хроматическое число неориентированного графа G можно эквивалентно определить как минимальное число вершин в неориентированном графе Я таком, что G имеет гомоморфизм в Я.
В дальнейшем рассматриваются орграфы без параллельных дуг. Отсюда следует, что при любой ориентированной раскраске концы любого пути длины два получают разные цвета. Ориентированная -раскраска орграфа G есть (ориентированный) гомоморфизм в -вершинный орграф Я. Ориентированное хроматическое число o(G) неориентированного графа G определяется как минимальное к, при котором каждая ориентация графа G имеет ориентированную -раскраску. Заметим, что ориентированное хроматическое число графа почти всегда существенно отличается от его хроматического числа. Например, существуют двудольные графы с произвольно большим ориентированным хроматическим числом (достаточно заменить каждое ребро графа Кп на путь длины 2, и тогда концы каждого такого пути в полученном графе К„, т. е. все вершины исходного графа Кп, обязаны краситься в разные цвета, т. к. в мишени нет антипараллельных дуг).
Ориентированная -раскраска орграфа G есть ориентированный гомоморфизм из G в некоторый fc-вершинный турнир Я (мишень), т. е. отображение р из V{G) в V(H), при котором ху Є E(G) =ї р(х)(р(у) Є Е(Н). Другими словами, вершины орграфа Я считаются цветами и требуется каждой вершине из G приписать цвет так, чтобы любая дуга в G, начало которой окрашено в цвет і, а конец — в ; , имелась бы в мишени Я.
При доказательстве того, что ориентированное хроматическое число всех графов, сколь угодно больших, из того или иного широкого класса ограничено сверху, приходится подыскивать мишень (одну для всех) минимального порядка, обладающую достаточно хорошими свойствами, согласованными со строением графов заданного класса. Обычно при этом в качестве мишени используются транзитивные турниры, в частности, известные в алгебраической комбинаторике турниры Пэли Р(4к + 3), где 4к+3 — простое число. В диссертации используется также отображение в другие турниры, например, С(5; 1,2).
Ориентированное хроматическое число было введено Курселем [11] при изучении логик второго порядка на графах. В частности, он доказал, что o(G) З63 для любого плоского графа G. Кроме того, ориентированное хроматическое число и его связи с другими параметрами графа изучались в [33, 36, 31, 27, 26, 8, 10, 6, 7]. В частности, граница З63 была улучшена в [33] до 80 (с использованием ациклической 5-раскрашиваемости плоских графов, доказанной в [5]), а в [27] было доказано, что, если подграф графа G имеет "большую" среднюю степень, то G имеет "большое" ориентированное хроматическое число. В связи с этим, в статье [10] рассматривались верхние границы на ориентированное хроматическое число графов с ограниченной максимальной средней степенью, mad(G) — maxccc \v{b}\ Нестрого говоря, mad(G) измеряет равномерную разреженность графа G: если mad(G) мала, то каждый подграф графа G "разрежен", т. е. имеет малую степень. Некоторые важные классы графов имеют ограниченную максимальную среднюю степень. Например, графы с большим обхватом и большим числом вершин, вложимые в фиксированную поверхность, как и плоские графы с большим обхватом, имеют низкую максимальную среднюю степень. А именно, для любого плоского или проективно плоского графа G с обхватом g, mad(G) -.
Теорема Пусть G - плоский граф обхвата g(G). Тогда (i) o{G) 19 при g(G) 5; (ii) o{G) 11 при g(G) Z 6; (iii)o{G) 7npng{G) 8; (iv) o{G) 5 при g{G) 14.
В [7] ограничение в п. 1 этой теоремы было ослаблено с 14 до 13. Наибольшее значение среди результатов главы 1 имеет доказанная в разделе 1.2
Этот вопрос оставался открытым примерно 10 лет. При доказательстве данной теоремы решающую роль сыграла новая идея глобального перераспределения эйлеровых вкладов, не встречавшаяся доселе в работах по плоским графам.
Отметим, что в нашей работе [52] эта теорема доказывается в более общем виде, а именно, мы доказываем, что любая ориентация графа (не обязательно плоского) с обхватом не менее 5 и максимальной средней степенью его подграфов менее 12/5 имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.
Здесь же укажем на связь между задачами ориентированной и круговой раскрасок. Для простоты приведем определение круговой раскраски неориентированного графа G в 5 цветов: требуется раскрасить его вершины цветами 0,1,..., 4 так, чтобы цвета любых двух смежных вершин отличались на 2 или 3 по mod 5, что эквивалентно существованию гомоморфизма графа G на цикл С5- Вопрос о круговой 5-раскрашиваемости плоских графов обхвата 12 также оставался открытым в течение нескольких лет. Нам удалось сначала доказать этот факт, а затем уже теорему 1.1. Оба доказательства имеют одинаковую структуру, но при доказательстве теоремы 1.1 пришлось преодолевать дополнительные трудности. Этот результат о круговой 5-раскрашиваемости остался неопубликованным, и его доказательство в диссертацию не включено. Возможно, не возникни вопрос о круговой 5-раскрашиваемости, так и теорема 1.1 не была бы доказана до сих пор, несмотря на усилия ряда исследователей из Франции, США, Чехии и других стран.
Наш главный результат состоит в дальнейшем усилении упомянутого результата об ориентированной 5-раскрашиваемости.
Фактически мы доказываем чуть более сильную форму теоремы 1.1, состоящую в том, что каждая ориентация графа G с mad(G) 12/5 и обхватом не менее 5 имеет ориентированный гомоморфизм в циркулянт С(5;1,2), т. е. в турнир на вершинах 0,1,2,3,4, в котором пара ij является дугой, если и только если j — і есть 1 mod 5 или 2 mod 5.
Требование на обхват здесь нельзя отбросить, как показывает граф G с mad(G) 12/5 и обхватом 4, состоящий из дуг ab, be, cd, de, ef, af и ad. Действительно, предположим, что G допускает гомоморфизм в циркулянт С(5;1,2). Без ограничения общности, можем считать, что а окрашена в 0, тогда для вершину d можно покрасить в 1 или 2 ввиду существованию дуги ad, но цепь abed запрещает на вершине d цвет 2, а цепь afed - цвет 1. Действительно, согласно циркулянту цвет конца любой дуги превышает цвет ее начальной вершины на 1 или 2 ( mod 5), поэтому за 3 шага по пути abed происходит увеличение цвета на величину от 3 до б ( mod 5), т. е. цвет 2 для вершины d невозможен. Итак, мы уже знаем, что d окрашена в 1. Однако, путь def запрещает на вершине / оба цвета 1 и 2, которые требует дуга af.
Основные структурные свойства минимального контрпримера
Пусть существует /г-цепь vo,Vi,...,vk,Vk+i, к 3, где Vi,v2,...,Vk — вершины степени 2, а степени вершин % Vk+i не менее 3. Удалим вершины иь v , v3 и возьмем ориентированную раскраску полученного графа (точнее гомоморфизм на С(5; 1,2)). Согласно замечанию 1 для v\ допустимыми (при фиксированной раскраске вершины VQ) ЯВЛЯЮТСЯ два цвета, для v2 — три цвета и т. д. Тогда для любого цвета вершины «4 можно последовательно подобрать цвета для вершин v3,v2, t i так, чтобы получилась ориентированная 5-раскраска графа Go. А именно, и4 диктует два возможных цвета на г?з, а на г з был один запрет (со стороны v2), следовательно г»з можно покрасить. Цвет вершины Уз был допустим относительно v2, т. е. на v2 существовал цвет, согласующийся (с учетом ориентации ребра v2v3) с выбранным уже цветом вершины v3, и мы его делаем цветом вершины v2. Аналогично красится vi. П
Назовем (ki,k2,.. .)-вершипой вершину, из которой исходят к\-, к2-,... цепи. Лемма 12. В Go нет ( 1,2,2)-вершин. ДОКАЗАТЕЛЬСТВО. Пусть v — ( 1,2,2)-вершина. Удалим v и 2-вершины инцидентных ей цепей. Согласно замечанию 1 по 1-цепи на v действует 2 запрета, а по 2-цепям — по одному. Следовательно для вершины v найдется такой цвет, при котором существует раскраска 2-вершин ценен, инцидентны о, си а иианная с гомоморфизмом. D Лемма 13. В Go нет циклов из ( 1, 1, 1)-вершин. ДОКАЗАТЕЛЬСТВО. Пусть такие циклы существуют и пусть С - кратчайший из этих циклов. Обозначим через V\, v2,..., Vk вершины степени 3 по часовой стрелке на С. Заметим, что две цепи, инцидентные каждой из V{, лежат на цикле С, а третья, внешняя, не может заканчиваться вершиной из С, поскольку цикл С минимален и g{Go) 5. Пусть wi - это 2-вершина не из С, смежная с Vi, a Sj - вершина, отличная от Vi и смежная с tUj. Удалим из Go все вершины цикла С, а также все ui{ и отобразим полученный граф на С(5; 1,2). Отметим, что 3-вершины цикла С могут соединяться как 1-цепями так и 2-цепями (понятно, что каждая 1-цепь имеет одну из 4 возможных ориентации: , «, О, X, а 2-цепь — 8). Случай 1. В С 3-вершины соединяются только 1-цепями. Согласно замечанию 1 для Vi допустимыми с точки зрения инцидентной ей внешней цепи, ведущей в Si, являются три цвета А{ = {а,-—1, а,-, сц+1}, т. е. при раскраске Vi в любой из них мы сможем подобрать цвет для Wi. Остается раскрасить все Vi в эти допустимые цвета так, чтобы мы смогли раскрасить 2-вершины самого цикла С согласно требованиям гомоморфизма на G(5; 1,2). Подслучай 1.1. Найдутся две последовательные 3-вершины цикла С, например, Vi,v2 такие, что соответствующие им тройки цветов А\ и А2 не являются (взаимно) жесткими. Тогда в А2 найдется цвет /?, универсальный для А\. Мы красим v2 в ft. Затем, пользуясь следствием 3, красим v3 так, чтобы можно было покрасить 2-вершину цикла С между v2 и v3. Аналогично красим весь С вплоть до вершины v\. Поскольку ни один из цветов, допустимых для v\, не конфликтует с цветом /3 вершины v2, мы можем теперь покрасить 2-вершину х\ между v% и г;2. Подслучай 1.2. При любом г тройки АІ и Лг+і являются (взаимно) жесткими. Если к, число 1-цепей в С четно, то вершины Vi при четном г красим в младшие цвета из ЛІ, а при нечетном і — в старшие. По лемме 3 полученная раскраска допускает продолжение до гомоморфизма всего Go на С(5; 1,2) посредством раскраски 2-вершин цикла С. Пусть теперь к нечетно. Тогда найдутся две соседние 1-цепи в С, например Р = VkXkVi и Q = V\X\V2, которые обе являются -цепями либо -цепями. Если Р и Q являются -цепями, то из А\ выбираем центральный цвет для Vi, а все остальные вершины Vi при нечетном г красим в старшие цвета из Д-, а все Vi при четном г — в младшие. По следствию 4 полученная раскраска допускает продолжение до гомоморфизма всего GQ на С(5; 1,2) посредством раскраски 2-вершин цикла С. Аналогично действуем, если Р и Q являются -цепями. Случай 2. В С существует 2-цепь, например, vixyv2 По замечанию 1, примененному последовательно к v\, х, у и v2, для каждого из двух крайних допустимых цветов на vi существует единственный цвет на v2, который не позволяет покрасить х и у, если Vi покрашен в соответствующий крайний цвет. Мы красим v2 в цвет, который не противоречит крайним цветам для v\, и вычеркиваем цвет с і из списка допустимых для v\. Далее красим цикл С по часовой стрелке начиная с и2, пользуясь следствием 3 при прохождении через 1-цепи и замечанием 1 — через 2-цепи (а именно, 2-цепь дает 1 запрет на раскраску своего конца, если другой уже окрашен). D Лемма 14. Депь из (1,1,1)-верлшя, начинающаяся в (2,1,1)-вершш/е, не может заканчиваться в (2,1,1)-вершине. ДОКАЗАТЕЛЬСТВО. Пусть существует квазицепь Р = voVi...VkVk+і, где Vi,V2,...,Vk — (1,1,1)-вершины, a VQ И Vk+x — (2,1,1)-вершины. По лемме 8 »о и Vk+i различны. Пусть Wi - это 2-вершина не из Р, смежная с v a st" вершина, отличная от v и смежная с W{. Через s 0 и s k+1 обозначим концы 2-цепей, инцидентных VQ и Vk+i соответственно. Не исключается, что s 0 = s k+v но ввиду леммы 8sJ / fjt+i и VQ ф s k+v Также из леммы 8 следует, что вершины so, si,..., Sk+i не принадлежат Р. Теперь будем считать, что квазицепь Р вложена в цепь Р = 7/0 0 0 1 1 2 Теперь мы видим, что лемма 9 является обобщением леммы 7.
Удалим из Go все вершины цепи Р , а также все Wi и раскрасим полученный граф. Согласно замечанию 1 от so (по 1-цепи) на VQ действует 2 запрета, а от s 0 (по 2-цепи) — один. Следовательно существует два таких цвета для вершины VQ, ЧТО в какой бы из них мы ни раскрасили г»о, мы всегда сможем раскрасить 2-вершины мо о Уо- Имея два допустимых цвета для VQ, МЫ имеем всего один запрет для vx, приходящий от VQ. Вместе с двумя запретами от Si для vi остаются 2 допустимых цвета (в какой бы из них мы ни раскрасили «1, мы всегда сможем раскрасить t 0 и 2-вершины Wi и її). Продолжая этот процесс, мы придем к тому, что Vk+і получает по одному запрету от г и s fc+1 и два запрета от sjt+і, т. е. Vk+i можно раскрасить. Далее красим вершины квазицепи Р в допустимые цвета в обратном порядке, а затем красим 2-вершины цепи Р и все вершины ги,-. D
Структурные свойства минимального контрпримера
Согласно лемме 14 в Go нет 3-вершины, смежной с 2-вершиной. Пусть v — 3-вершина, смежная с 3-вершинами и, w, х. Если все дуги при v входящие либо все выходящие, то удаляем v и рассматриваем раскраску полученного графа. Если цвета вершин щ w, х попарно различны, то по п. 3 леммы 1 для v имеется 4 допустимых цвета, а в случае совпадения цветов на и, w, х допустимых цветов для v либо 11, либо 23.
Пусть теперь дуга из х входит в и, а из и выходят дуги в и и ю. Тогда мы заменяем v и инцидентные ей ребра на пути xv\u и XV2W, ориентированные от х, где «і, V2 — вершины степени 2. Заметим, что в полученном графе тяжелых ребер меньше, чем в Go, хотя общее число ребер больше, поэтому существует гомоморфизм с полученного графа на Р(47). Заметим, что с(и) ф с(х) ф с(го). Перенесем раскраску с на Go; теперь по лемме 1 для v существует 4 допустимых цвета, если с(и) ф c(w), и 11 — в противном случае. Для других ориентации дуг при вершине v доказательство аналогично. D
Назовем вершину v особой, если do(v) = 3, di(v) = 4 и при и существует единственная грань вида / = axvyc..., где х, у — вершины степени 2. Например, на рис. 1 все вершины, инцидентные в точности трем 0-цепям, являются особыми.
Назовем б-грань особой, если она инцидентна трем 1-цепям. Отметим, что на рис. 1 каждая особая грань инцидентна трем особым вершинам, хотя, вообще говоря, особая вершина не обязана быть инцидентной особой грани и, наоборот, особая грань может быть не инцидентна ни одной особой вершине.
Пусть сначала d0{v) = 3. Тогда по лемме 15 вершина v инцидентна хотя бы одной 2-вершине t Удалим t и перенесем раскраску полученного графа на Go. Обесцветим вершины и, и, ад и все 2-вершины, смежные с ними.
Согласно лемме 1 вершина и имеет 11 вариантов раскраски, не противоречащих цветам двух уже окрашенных смежных с нею 3-вершин графа Go. Учитывая инцидентность вершины и трем 1-цепям, ведущим в уже окрашенные вершины, мы получаем множество U цветов, допустимых для и, где \U\ 11 — 3 = 8. Аналогично определяется множество W мощности не менее 8. Чтобы не возникло конфликта между единственной смежной с v окрашенной вершиной х, мы вычеркнем цвет вершины х из множеств U и W. Полученные множества мощности не менее 7 обозначим через U и W, соответственно. Ввиду наличия вершины z, мы должны выбрать для и и w по одному цвету, с(и) и c(w) из множеств U и W так, чтобы с(и) ф c(w).
Для этого выделим в U и W независимые подмножества U" и W", соответственно, мощности 3 каждое. По лемме 2 множества U" и W" дают по 7 запретов на выбор цвета для вершины v. Поскольку х разрешает для v не менее 23 цветов, то не менее 23 - 7 — 7 = 9 цветов должны присутствовать на концах 1-цепей, инцидентных v. Действительно, в противном случае мы красим в допустимые цвета сначала v, затем и и w, а потом все 2-вершины, смежные с ними. (2) Пусть теперь do( ) = 4. Обозначим через хну отличные от и, w вершины степени не менее 3, смежные с v. Удалим 2-вершину z и перенесем раскраску полученного графа на Go- Обесцветим вершины и, v, w и все 2-вершины, смежные с ними. Замечание 17. Если бы ребра uv и vw образовывали путь (uvw или wvu), то для доказательства леммы достаточно было бы покрасить вершину z, а это возможно ввиду леммы 1. Поэтому будем считать, что ребра uv и vw ориентрованы либо оба к v, либо оба от v. В зависимости от ориентации четырех тяжелых ребер, инцидентных v, мы оказываемся в одной из трех ситуаций, описанных в леммах 4, б, 7. Случай 1. Оба ребра xv и yv по отношению к вершине v сориентированы иначе чем ребра uv и vw (либо первые два заходят в и, а вторые — выходят, либо наоборот). Определим множества U и W как п. 1 настоящей леммы. Чтобы не возникло конфликта между одной из вершин х, у и одной из вершин и, їй, мы вычеркнем цвета а и /? вершин хну, соответственно, из множеств U и W (в предположении, что а ф /3, поскольку иначе можно воспользоваться леммой 1: пусть а = /?; тогда зафиксируем цвет 7 из множества U, отличный от а, а затем цвет 6 из W, отличный от а и 7)- Полученные множества мощности не менее б обозначим через U и W, соответственно. Ввиду наличия вершины z, мы должны выбрать для иишпо одному цвету с(и) и c(w) из множеств U и W так, чтобы с(и) ф c(w). Если V = W, то можно воспользоваться леммой 3. Действительно, если d\ (и) 3, то мы красим в допустимые цвета сначала v, затем uuw,a потом все 2-вершины, смежные с ними. Пусть U ф W. Тогда выделим в U и W независимые подмножества U" и W" мощности 4 и 3, соответственно (сначала внесем в U" элемент 71 из U \ W, а в W" элемент #i из W \ V; далее если в U \ {71} и W \ {Si} есть один и тот же элемент, то включаем его в U" (а иначе уже нечего доказывать), а следующий общий элемент в оставшихся подмножествах, если таковой имеется, включаем уже в W", и т. д.). Теперь остается воспользоваться леммой 4. Случай 2. В точности одно из ребер xv и yv, пусть yv, сориентировано по отношению к вершине v так же, как ребра uv и vw. Теперь мы вычеркнем из множеств U и W (напомним, что мощность каждого из них не менее 8) только цвет а вершины х. Далее, если цвет @ вершины у (заметим, что J3 ф а) не принадлежит множеству U U W, то действуем полностью аналогично доказательству случая 1. Единственное различие возникает лишь если \U f\ W \ 5, т. е. нельзя воспользоваться леммой 3: тогда сначала внесем в U" два элемента из U \ W, а в W" — два элемента из W \ V. В конце воспользуемся леммой 6.
Предположим теперь, учитывая симметрию между U и W, что /З Є W. Тогда на вершине w зафиксируем цвет /3, а на вершине и — цвет из U, отличный от а и /3; после чего можно воспользоваться леммой 1, т. к. одинаково окрашенные вершины yaw при одинаково направленных ребрах yv и wv можно рассматривать как одну вершину.
Случай 3. Оба ребра xv и yv сориентированы по отношению к вершине v так же, как ребра uv и vw.Теперь между вершинами х, у, и и w конфликтов нет. Поэтому если а ф р и {а,Р} П (U U W) = 0, то мы пользуемся леммой 8 в случае когда \U Г) W\ 5 (начиная построение множеств U" и W" с независимых троек, а потом расширяя их до независимых множеств нужной мощности), а в противном случае — леммой 3.
Вырожденные варианты разбираются, как в случае 2, с использованием леммы 1. А именно, если а = /3, то вершины х и у "склеиваются", а на и и w фиксируется 2 различных цвета, отличных от а. Пусть а ф J3, но, скажем, а Є U; тогда и окрашивается в а и отождествляется с х, а на и/ выбирается цвет, отличный от а и /9. D
Структурные свойства минимального контрпримера
Удалим перечеркнутое ребро на рис. 2 (а) и обесцветим вершины V\, v% и vz-Пусть z окрашена в цвет 1. Заметим, что v\ нельзя покрасить лишь в том случае, когда на вершине и и смежных с ней вершинах встречаются все А цветов (т. е. для Vi остается только цвет 1). В этом случае перекрасим вершину х в 1 (это всегда возможно, так как вершина у находится на расстоянии 2 от г, а следовательно, не окрашена в 1), а г х — в освободившийся цвет. Последними красим г»г и г/3 (у них по 4 ограничения на выбор цвета).
Доказательство аналогично доказательству утверждения (і), с той лишь разницей, что нет вершины Vz (см. рис. 2 (b)). DЛемма 3. В G нет пучка,, ограниченного с обеих сторон вершинами степени меньше Д.
ДОКАЗАТЕЛЬСТВО. Удалим перечеркнутое ребро и обесцветим его концы (см. рис. 3). Пусть d(w) Д—1 и d(v) Д—1. Покрасим один из концов ребра, например, у (на него действует не больше Д ограничений). Заметим, что х нельзя покрасить лишь в том случае, когда для х остается только цвет, занятый на у. В этом случае покрасим х в цвет вершины z, a z перекрасим в цвет вершины у (в дальнейшем такую операцию, встречающуюся уже в лемме 2, будем называть подкруткой). О
Доказательство. Пусть d(v) А — 5, тогда d(w) = Д (по лемме 3). Удалим перечеркнутое ребро и обесцветим вершину v, все 2-вершины пучка В, центральные вершины особых 3-цепей и все смежные с v вершины, кроме лежащих на жестких 1-цепях (см. рис. 4). Пусть к — толщина пучка В. Покрасим v в один из цветов, встречающихся на w или на оставшихся окрашенными вершинах, смежных с го. Имеется Д — к + 1 таких цветов, а на выбор цвета для v имеется не более d(v) -к+ 5 Д - к ограничений (поскольку есть не больше пяти неособых жестких 1-цепей, которые дают, по два ограничения, тогда как остальные неособые цепи - одно ограничение, а две цепи каждой особой грани вместе дают два ограничения), т. е. v всегда можно покрасить в цвет вершины го или ее соседей. Затем красим смежные с w вершины из В (на последнюю имеется Д ограничений, т. к. цвет вершины v встречается дважды); а потом — смежные с v вершины (что возможно, т. к. d(v) Д - 5) и, наконец, центральные вершины особых 3-цепей.
Доказательство. Пусть d(v) Д - 29, тогда d(w) = Д (по лемме 3). Удалим перечеркнутое ребро и обесцветим вершину v, все 2-вершины пучка В, центральные вершины особых 3-цепей и все смежные с v вершины, кроме лежащих на непучковых цепях (см. рис. 5). Пусть к — толщина пучка В. Покрасим v в один из цветов, встречающихся на w или на оставшихся окрашенными вершинах, смежных с го, таких цветов Д — к +1. А на выбор цвета для v имеется не более d(v) — /г + 29 Д — к ограничений (ввиду того, что v не является сильной, непучковых цепей имеется не более 29, и они дают не более чем по два ограничения, тогда как пучковые цепи -одно ограничение), т. е. v всегда можно покрасить в цвет вершины ги или ее соседей. Затем красим смежные с го вершины из В (на последнюю имеется Д ограничений, т. к. цвет вершины v встречается дважды); затем — смежные с v вершины (что возможно, т. к. d(v) Д — 29), и наконец, центральные вершины особых 3-цепей. П
Пусть в G имеется пучок В толщиной . На рис. 6 удалим перечеркнутое ребро И Обесцветим ВСЄ 2-ВерШИНЫ Пучка И ЄГО КОНЦЫ Vi И V2 Тогда на выбор цвета для каждой из вершин v\ и v2 имеется не более — ограничений, следовательно найдется цвет, в который можно покрасить и их, и v2, что мы и сделаем. Пусть все вершины пучка, кроме х, окрашены (это возможно, так как на каждую имеется не более А ограничений). Вершину х нельзя покрасить только в том случае, когда для нее остается только цвет а (см. рис. б). В этом случае делаем подкрутку: перекрашиваем у в а, а освободившийся цвет используем для х. О
Доказательство. Если бы b(v) = 1, то по следствию 3 и лемме 4 v имела бы не менее Д — 4 — 13 непучковых цепей, что невозможно для слабой вершины. Итак, мы доказали, что b(v) 2.
Из определения слабой вершины имеем b(v)+dur(v)+dq(v) 7— 7, откуда dur(u)+dq(v) 5, но жестких неособых цепей dur(v), а жестких особых в точности d4(v) по лемме 2, следовательно жестких 1-цепей не более четырех. D
Лемма 5. В G нет слабой вершины, инцидентной пучку толщины у ДОКАЗАТЕЛЬСТВО. Удалим перечеркнутое ребро (см. рис. 6) и обесцветим слабую вершину Vi и второй полюс щ пучка В, все младшие вершины на расстоянии 2 от vi и V2, а также все смежные с v\ и v вершины, кроме тех, что лежат на инцидентных им жестких 1-цепях. Тогда на выбор цвета для vi имеется не более чем - + 4 ограничений, для v% — не более чем - х 2, а всего Д ограничений. Следовательно, найдется цвет, в который можно покрасить и Vi, и г 2, после чего действуем, как в доказательстве леммы 4. D
По следствию 4 слабая вершина v инцидентна не менее чем двум пучкам. Удалим перечеркнутое ребро и обесцветим v, все смежные с ней вершины и младшие концы 1-цепей. Пусть конец одного из пучков окрашен в 1.
Если вершину v можно покрасить в 1, то раскраску можно продолжить следующим образом: раскрасим сначала непучковые вершины, смежные v, а потом 2-вершины в пучках, аналогично доказательству леммы 4, применяем подкрутку. Последними красим младшие вершины.
Если v нельзя покрасить в 1, то имеет место ситуация, изображенная на рис. 7, где фиксированные цвета отмечены кружком. В этом случае покрасим в 1 одну из смежных с v вершин (см. рис. 7). Далее действуем, как в предыдущем случае. Вершину и красим последней; если для и остается только цвет 2, применяем подкрутку. Последними снова красим младшие вершины.
