Содержание к диссертации
Введение
1. Общая характеристика работы 3
2. Основные определения и обозначения 6
3. Краткий обзор результатов диссертации 10
1. Строение младших граней эйлеровых многогранников 14
1.1. Формулировка основного результата главы 14
1.2. Доказательство теоремы 1.1 17
2.2-дистанционная раскраска плоских графов 30
2.1. Обзор результатов главы 30
2.2. Доказательство теоремы 2.1 31
2.2.1. Случай д > 9 32
2.2.2. Случай д = 7 41
2.3. Доказательство теоремы 2.2 48
2.3.1. Структурные свойства минимального контрпримера 49
2.3.2. Окончательное распределение зарядов и его следствия 57
3. Задача (р, д)-раскраски плоских графов 64
3.1. Обзор результатов главы 64
3.2. Доказательство результатов о (р,
3.3. Доказательство результатов о предписанной (р, #)-раскраске 69
Список литературы 74
- Краткий обзор результатов диссертации
- Структурные свойства минимального контрпримера
- Окончательное распределение зарядов и его следствия
- Доказательство результатов о предписанной (р, #)-раскраске
Введение к работе
1. Общая характеристика работы
Задачи раскраски графов интересуют многих специалистов не только по теории графов и дискретной математике, но и физиков, программистов, экономистов и других. Этот интерес вызван тем, что задачи о раскрасках графов имеют разнообразные приложения, в частности, в задаче назначения радиочастот в сетях мобильного телефонирования, в задаче оптимальной организации структуры баз данных, распределения ресурсов, в задачах, возникающих при планировании производства, составлении графиков осмотра и хранения товаров и т. д.
Наиболее широко известной из задач раскраски графов является знаменитая проблема четырех красок (1852 г.): требуется доказать возможность раскрасить плоскую карту четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Доказательство было дано более чем через 120 лет К. Аппелем и В. Хакеном [12, 13, 14]. Решение состояло в построении так называемой "неизбежной системы сводимых конфигураций", а именно в нахождении такой системы структурных фрагментов, что хотя бы один из них содержится в каждом графе рассматриваемого класса, причем каждая из этих конфигураций является сводимой, т. е. должна отсутствовать в минимальном контрпримере к данной задаче о раскраске. Метод сводимых конфигураций применяется для решения подавляющего большинства задач раскраски плоских графов. Наиболее полную информацию о результатах в области раскраски графов, полученных до середины 90-х годов прошлого столетия, можно найти в книге В. Тофта и Т. Р. Йенсена [25].
Отметим, что первоначально большинство фактов о строении плоских графов, установленных при решении задач о раскрасках, использовались только в рамках рассматриваемой задачи, т. е. интерес к локальным свойствам графов возникал только применительно к задачам раскраски. Один из первых шагов в изучении структуры плоских графов был сделан А. Лебегом в 1940 г. Созданная А. Лебегом [30] теория эйлеровых вкладов, основанная на преобразовании известной формулы Эйлера для многогранников, в дальнейшем получила широкое применение и развитие в работах
А. Коцига [27]-[29], Б. Грюнбаума [21]-[23] и других. Последующие важные шаги в становлении структурной теории плоских графов были сделаны О. В. Бородиным, в частности, в [7, 9, 10, 8,19]. Перечисленные, а также и многие другие работы по раскраскам плоских графов позволили теоремам о строении плоских графов выступить уже в роли самостоятельного объекта изучения, заложив основу структурной теории плоских графов. Введение в эту теорию представлено в докторской диссертации О. В. Бородина [7].
Заметим, что структурные теоремы, полученные в перечисленных выше работах, касаются плоских графов с минимальной степенью 5^3. Что же касается плоских графов с 5 = 2, то, хотя об их строении известно довольно много, стройной классификации этих графов в настоящее время пока нет. Интерес к изучению строения плоских графов с 5 = 2 вызван возможностью применения структурных свойств этих графов к некоторым видам раскраски графов, в частности, реберной, тотальной, 2-дистанционной, (р, д)-раскраске, ориентированной, предписанной и других.
В диссертации рассматриваются (р, д)-раскраска и частный случай этого вида раскраски, 2-дистанционная, разреженных плоских графов (имеющих заданный обхват), при изучении которых мы сталкиваемся с графами, имеющими 5 = 2.
Задача (р, #)-раскраски плоских графов является одной из основных моделей в проблеме распределения радиочастот в сетях мобильного телефонирования, когда источники (вершины плоского графа) должны получить целочисленные частоты (быть раскрашены) так, чтобы цвета вершин, расстояние между которыми равно 1, различались не менее чем на р, а на расстоянии 2 — не менее чем на q. Поскольку частоты близко расположенных источников должны различаться сильнее ввиду интерференции волн, то р ^ q.
Цель настоящей работы состоит в получении новых результатов о строении младших граней в 3-многогранниках и (р, (^-раскраске (в том числе и предписанной) разреженных плоских графов, причем в диссертации большое внимание уделяется наиболее важному частному случаю этой раскраски — 2-дистанционной.
Результаты работы носят теоретический характер. Результаты о (р, (^-раскрасках плоских графов в перспективе могут быть использованы при решении проблемы распределения радиочастот в сетях мобильной связи.
Основные результаты диссертации:
Уточнен один из параметров теоремы Бородина (2002 г.), усиливающей теорему Лебега (1940 г.) о строении младших граней 3- многогранников.
Получены достаточные условия 2-дистанционной раскрашиваемости плоских графов с заданным обхватом в число цветов, совпадающее с тривиальной нижней границей Д + 1; определенное условие на обхват является неулучшаемым.
3. В дополнение к результатам п. 2, при д = 6 найден класс 2-дистанционно
(Д + 1)-раскрашиваемых плоских графов; они имеют Д ^ 31, а каждое ребро в
них инцидентно вершине степени 2.
W 4. Для планарного графа G достаточно большого обхвата доказаны верхняя и
нижняя оценки его (р, (^-хроматического числа (как предписанного, так и обычного), которые отличаются друг от друга на величину, не зависящую от р.
В диссертацию включены лишь те результаты совместных работ [37] - [45], которые получены диссертантом.
При получении результатов диссертации были использованы метод сводимых
конфигураций и метод перераспределения эйлеровых вкладов.
^ По теме диссертации опубликованы 7 журнальных статей [37, 38, 39, 41, 42, 43,
44], одна статья в трудах конференции [40] и заметка в сборнике докладов ]45].
Диссертация состоит из введения, трех глав и библиографии, содержащей 45 наименований.
Результаты работы докладывались в 2006 г. на X Лаврентьевских чтениях Республики Саха (Якутия) и IV Всероссийской школе-семинаре студентов, аспирантов, молодых ученых и специалистов "Математическое моделирование развития север-Щ ных территорий РФ" и подробно обсуждались на научном семинаре лаборатории теории графов Института математики СО РАН в 2004-2006 гг. Работа автора по раскраске плоских графов в 2005-2007 гг. поддержана грантом РФФИ 05-01-00816. Автор в 2006 г. за работу по теме диссертации получил Государственную стипендию Республики Саха (Якутия) для молодых ученых и аспирантов.
Автор выражает благодарность своему научному руководителю О. В. Бородину
за постановку задач и всестороннюю поддержку, А. Н. Глебову за внимательное про-
Йк чтение рукописей большинства статей и полезные обсуждения и советы, А. О, Ива-
новой за помощь в подготовке диссертации, а также всем сотрудникам лаборатории теории графов Института математики СО РАН.
2. Основные определения и обозначения
В настоящем разделе дадим определения используемым понятиям и терминам, а также введем обозначения, используемые в диссертационной работе. Заметим, что определения некоторых понятий будут даны отдельно, в рамках того раздела, в котором они будут использоваться. Отметим также, что в данной работе будут рассматриваться только обыкновенные графы, т. е. неориентированные графы без петель и кратных ребер.
Запись G = G(V,E), означает, что граф G есть совокупность непустого множества вершин V и множества ребер Е (неупорядоченных пар различных элементов множества V). Множество вершин графа G обозначается через V(G), а множество его ребер через E(G). Ребро е, соединяющее вершины и и v, записывается как е = uv (или просто uv), при этом говорят, что вершины и тли инцидентны ребру е. Две вершины и и v в G называются смежными, если uv Є E(G). Два ребра, инцидентные одной и той же вершине, называются смежными. Если существует такое разбиение множества вершин V графа G на две части (доли), что концы каждого ребра принадлежат разным долям, то G называется двудольным. Двудольный граф называется полным, если любые две вершины этого графа, находящиеся в разных долях, смежны, и обозначается через Кт;п, если две его доли содержат соответственно т и п вершин. Полный двудольный граф К1іП называется звездой.
Число инцидентных вершине v Є V{G) ребер из E(G) называется степенью вершины г; в G и обозначается через d(v). Под d-вершиной понимается вершина степени d. Вершина называется младшей, если ее степень не больше 5. Висячей называется вершина степени 1. Минимальная степень вершин графа G обозначается через 5(G), а максимальная — через A(G).
Если U — произвольное подмножество вершин графа G, то через G — U обозначается подграф в G, получаемый удалением из G всех вершин подмножества U и инцидентных им ребер. При U = {v} вместо G-{v} будем писать G — v. Аналогично
определяется граф G - uv.
Цепью Р = (V,Е) называется граф вида V = {v0,vi,...,vn}, Е = {v0vi,ujV2, , Vn-iVn}, где все ребра различны. При этом говорят, что Р есть цепь из vQ в vn, а сама цепь имеет длину п. Цепь Р обычно задается как последовательность ее вершин, т. е. Р = г/о^і.. .vn. Замкнутая цепь Р — v$V\.. .vn (при Vq = vn) при n > 3 называется циклом длины п и обозначается через С = (v\V2 .. vn). Если в цепи Р и цикле С все вершины Vi различны, то Р и С называется соответственно простой цепью и простым циклом. Любая простая цепь с концами в вершинах инь называются (и — и)-цепъю. Под п-циклом понимается любой простой цикл длины п, а простой цикл длины 3, 4, ... называется треугольником, четырехугольником и т. д. Граф без циклов называется ациклическим графом или лесом.
Длина кратчайшей (и — г>)-цепи в G есть расстояние между вершинами и и v и обозначается через d(u, v). Если для вершин и и v нет ни одной такой цепи, то полагают d(u,v) = со. Если же для любых двух вершин и и v графа G существует (и—г>)-цепь, то G называется связным графом. Длина минимального цикла в графе G называется его обхватом g(G) (если в G нет циклов, то g(G) = со). Отметим, что для плоского графа обхват является одной из мер его разреженности. Граф G называется fc-связным, если G связен и граф G — U связен для любого U С V с \U\
Вершинная раскраска графа G = (V, Е) — это отображение : V -» С такое, что ір(и) ф
Если для каждой вершины v графа G задан свой собственный список допустимых цветов L(v) С С, где С — множество цветов, причем \L(v)\ = к, то тогда говорят, что на множестве вершин V(G) задано предписание L размера к. Граф G называется предписаний к-раскрашиваемым, если для любого множества С и любого предписания L размера к существует раскраска tp : V(G) —» С такая, что ip(v) Є L(V) для
любой вершины v графа G. Наименьшее целое к такое, что граф G является предписание А;-раскрашиваемым, называется его предписанным хроматическим числом и обозначается через \l''(G).
Раскраска V(G) —» {0,1,..., к - 1} графа G = (V, Е) называется (р, q)-pac-краской, где р и q — неотрицательные целые числа такие, что р > q, если для любых вершин v и w графа G выполняются условия: \
Граф G = G(V,E) называется плоским, если V(G) — это точки плоскости, а E(G) — жордановы кривые, соединяющие пары вершин, причем различные кривые пересекаются только в своих общих концевых вершинах. Граф, изоморфный какому-нибудь плоскому графу, называется планарным. Области, на которые плоскость разбивается вершинами и ребрами плоского графа G, называются гранями G. Образующаяся при этом разбиении единственная бесконечная область называется внешней гранью. Множество всех граней плоского графа G обозначается через F(G) — F. Если в плоском графе все грани имеют ранг 3, то граф называется триангуляцией.
У связного плоского графа G каждая грань ограничена некоторым (не обязательно простым) циклом, который называется граничным циклом грани /. Рангом грани / называется длина ее граничного цикла и обозначается через r(f). Под г-гранью понимается грань ранга г. Грань называется младшей, если ее ранг не больше 5. Если вершина v Є V(G) (ребро є Є E(G)) принадлежит граничному циклу грани / Є F(G), то говорят, что вершина v (соответственно е) инцидентна (инцидентно)
грани /. Две грани называются смеоюными, если инцидентны одному и тому же ребру.
Плоский граф G называется плоской нормальной картой, если степень любой вершины и ранг каждой грани G не меньше 3. По теореме Э. Штейница [34] эйлеровы многогранники (конечные выпуклые многогранники в R3) взаимно однозначно соответствуют 3-связным плоским графам (далее называемые 3-многогранниками).
Для любого плоского графа G = (V, Е, F) справедлива формула Эйлера
\V\-\E\ + \F\ = 2. (1)
Данная формула может быть преобразована следующим образом:
{{g-2)\E\-g\V\) + {2\E\-g\F\) = -2g, (2)
где д = g(G),
Отсюда, используя лемму о рукопожатиях, из равенства (2) мы получаем:
Е(^гф)-5)+Вг(я- (з)
vV /eF
где d(v) — степень вершины v, а г(/) — ранг грани /.
Назовем в (3) зарядом [x(v) вершины v графа G величину, равную ^(1(и) - g, а зарядом /х(/) грани / графа G величину г(/) — д. Тогда неравенство (3) запишется в виде:
Е ^ < - (4)
xeVUF
При доказательстве наших утверждений о плоских графах мы будем допускать существование минимального контрпримера (по числу ребер), относительно которого будем рассматривать (4). Далее мы будем перераспределять заряды, не изменяя их суммы, таким образом, чтобы новый заряд ц* каждой вершины и грани оказался неотрицательным, что приведет к противоречию
о < е №) = Е ^ < -
xuWF xeVuF
Рассмотренный нами подход к доказательству утверждений называется методом перераспределения эйлеровых вкладов (зарядов).
3. Краткий обзор результатов диссертации
В первой главе изучается структура 3-многогранников, а именно строение их младших граней (т.е. ранга не выше 5).
В 1940 г. А. Лебег [30] показал, что в любом 3-многограннике есть грань, набор степеней вершин которой, мажорируются одной из следующих последовательностей:
. (3,6, оо), (3,7,41), (3,8,23), (3,9,17), (3,10,14), (3,11,13), (4,4, оо), (4,5,19), (4, б, 11), (4,7,9), (5,5,9), (5,6,7), (3,3,3,00),(3,3,4,11),(3,3,5,7),(3,4,4,5),(3,3,3,3,5).
Некоторые параметры этого описания позднее были уточнены для отдельных классов 3-многогранников. Но вплоть до 2002 г. [10] ни один из этих параметров не был улучшен без ухудшения других ее параметров. В работе [10] О. В. Бородиным было получен следующий результат, усиливающий теорему Лебега.
Теорема (Бородин, [10]). Каждый 3-многогранник содержит грань одного из следующих типов:
(3,6, оо*), (3,8*, 22), (3,9*, 15), (3,10*, 13), (3,11*, 12),
(4,4, оо*), (4,5*, 17), (4,6*, 11), (4,7*, 8), (5,5*, 8), (5,6, б*),
(3,3,3, оо*), (3,3,4*, 11), (3,3,5*, 7), (3,4,4,5*), (3,3,3,3,5*).
Звездочкой помечены те вхождения, неулучшаемость которых была доказана, причем в каждом типе граней компоненты, предшествующие помеченным, также неулучшаемы.
В [10] была поставлена задача: найти уточнение теоремы Лебега, не допускающее дальнейших усилений. Заметим, что решение этой задачи требует уточнения небольшого числа параметров.
В диссертации сделан один шаг в этом направлении, а именно, член (4,5,17) заменяется на (4,5,16).
Во второй главе представлены результаты о 2-дистанционной раскраске разреженных плоских графов.
Раскраска вершин графа G называется 2-дистанционной, если любые две вершины, находящиеся друг от друга на расстоянии не более 2, получают разные цвета.
Наименьшее число цветов в 2-дистанционной раскраске графа G называется 2-дис-танционным хроматическим числом графа G и обозначается через X2(G).
Существует гипотеза Г. Вегнера (1977 г.) [36] о том, что Xi{G) ^ |JA(G)J +1 для любого плоского графа G с максимальной степенью A(G). Первый результат в этом направлении был получен Я. Ван-ден-Хойвелом и С. Мак Гиннессом [35], доказавшим что X2(G) < 2Д + 25. В [9] О. В. Бородин, А. Н. Глебов, X. Брусма и Я. Ван-ден-Хойвел доказали, что для произвольных плоских графов Xi{G) < [|A(G)]+1 при A(G) ^ 47, что улучшило оценку Г. Агнарсона и М.М. Холдорсона [11]: X2(G) ^ < L|A(G)J+2 при A(G) ^ 749.
Для любого графа G с максимальной степенью А очевидной нижней оценкой для Х2 является А +1, так как А +1 есть необходимое число цветов для 2-ди станционной раскраски А-звезды, содержащейся в любом графе. В частности, эта оценка достигается на всех деревьях, но не достигается, например, на циклах С^+\-
Вопрос о том для сколь малых д (обхват графа) можно гарантировать равенство X2(G) — А + 1 путем наложения ограничения только на А был полностью решен в [37, 38]. В диссертацию включены только те результаты из работ [37, 38], которые были получены самим диссертантом. Основным результатом является теорема 2.1, доказанная в разделе 2.2.
Теорема 2.1. Пусть G — планарный граф, тогда X2(G) = А + 1 в каоїсдом из. следующих случаев: (i) А = 4 и g > 15; (ii) А = 5 и g > 13; (iii) А = б и g ^ 12; (iv) А ^ 7 и g Z 11; (v) А > 9 и g = 10; (vi) А ^ 16 и g = 9; (vii) А ^ 30 ид = 7.
В [38] было показано существование плоских графов с д ^ 6, для которых Х2 > > А + 1 при произвольно большом Д. Таким образом, определенное нами условие на обхват, д > 7, является неулучшаемым для 2-дистанционной (А 4- 1)-раскраши-ваемости плоского графа. Отметим, что доказательство утверждения (vii) в теореме
2.1 было технически наиболее сложным.
Ввиду сказанного в предыдущем абзаце для обеспечения 2-дистанционной (Д + 1)-раскрашиваемости плоского графа G обхвата б потребовалось ввести дополнительное структурное требование: хотя бы один из концов каждого ребра графа G является вершиной степени 2. В [39] было доказано, что если G — плоский граф обхвата б, в котором A(G) ^ 179, а каждое ребро инцидентно 2-вершине, то X2{G) = A(G) + 1. В диссертации этот результат был усилен следующим образом.
Теорема 2.2. Если G — плоский граф обхвата 6, е котором A(G) ^ 31, а каждое ребро инцидентно 2-вершине, то Xi{G) = A(G) + 1.
Третья глава содержит результаты о (р, q)- и предписанной (р, д)-раскрасках плоских графов достаточно большого обхвата.
Раскраска вершин графа G называется (р, д)-раскраской, если вершины графа G, расстояние между которыми равно 1, получают цвета, отличающиеся друг от друга не менее чем на р, а на расстоянии 2 — не менее чем на q. Если при этом для каждой вершины задан список допустимых цветов, то говорят о предписанной (р, д^-раскраске. Наименьшее число цветов в (р, д)-раскраске графа G называется (р, «^-хроматическим числом графа G и обозначается через Xp,q{G). Аналогично определяется предписанное (р, ^-хроматическое число Xlp,q{G)-
Понятно, что ранее рассмотренная 2-дистанционная раскраска является в точности (1, 1)-раскраской.
Для (р, р)-хроматического числа произвольного графа G имеем очевидную нижнюю оценку: Xp,p(G) ^ Ар + 1 (из тех же соображений, что и для (1,1)-раскраски). Заметим, что всегда Хр,р{@) ^ Р Хід — V + 1> так как минимальную (1,1)-раскраску цветами 0,1,..., Хід—1 можно преобразовать умножением всех ее цветов нар в {р,р)-раскраску цветами 0,р,..., (хід — 1)р. Поэтому, ввиду теоремы 2.1, можно утверждать, что если G — плоский граф обхвата не меньше 7, то Хр,р(@) = Ар + 1 при Д>30.
О. В. Бородин, А. Н. Глебов, X. Брусма и Я. Ван-ден-Хойвел [9] доказали для произвольного плоского графа G, что Xp,q{G) ^ Юр + сь где С\ — величина, не зависящая от р.
Для разреженного же плоского графа в случае р > q ^ 1 в диссертации доказы-
вается
Теорема 3.1. Пусть G — планарный граф обхвата не менее 31. Тогда xM(G) ^ < 2р + (Д(0 - 1)(2^ - 1) гс;ш Д(С?) > 5.
Ясно, что при р 3> 5 данная оценка лучше той, что приведена выше для р = q. Что касается нижней оценки (р, «^-хроматического числа, то доказано
Предложение 3.2. Существуют такие плоские графы G произвольного обхвата со сколь угодно большим А, что Xp,q(G) ^ 2р + 1 + (А - 2)q.
Таким образом, при р^> q главный член, равный 2р, в теореме 3.1 не допускает улучшения.
Очевидно, что Xp,q(G) ^ Xp,q(G) Для любого графа G. При q = 0 величина xp,q{G) может сколь угодно сильно отличаться от Xp,g(G)-
Предложение 3.3. Для любого п ^ 1 существует граф G такой, что Xp,o(G) = = P + l,aXlPio(G)>n(2p-l).
Что касается предписанных (р, д)-раскрасок при q ^ 1, то вопрос о существовании графа G, для которого Xp,q(G) Ф Xp,q{^)> остается открытым (аналогичный вопрос известен много лет для реберной и тотальной раскрасок). Для произвольных плоских графов в [9] доказана та же оценка: Xp,q(G) ^ Юр + сь что и Для Xp,q(G). Для предписанного (р, (^-хроматического числа в диссертации доказывается та же верхняя оценка, что и для обычной (р, д)-раскраски, а именно
Теорема 3.4. Пусть G — планарный граф обхвата не менее 5([(Д/С^|2 _^] + + 4) + 1. Гогпри A(G) > 4.
Отметим, что ограничение на обхват в теореме 3.4, в отличие от теоремы 3.1, является растущей функцией от р при фиксированных q и A(G). Следующий факт частично объясняет это обстоятельство.
Предложение 3.5. В задаче предписанной (р, q)-pacnpacKu в 2p+(A(G)-l)(2q— —1) цветов k-цепь, где к ^ 2[,д,с/~?,2 .J+1, не является сводимой конфигурацией при A(G) > 2.
Следовательно, определенные нами достаточные условия для предписанной (р, q)-раскрашиваемости оказываются, вообще говоря, более жесткими, чем для обычной (р, д)-раскраски в одно и то же число цветов.
Краткий обзор результатов диссертации
В первой главе изучается структура 3-многогранников, а именно строение их младших граней (т.е. ранга не выше 5). В 1940 г. А. Лебег [30] показал, что в любом 3-многограннике есть грань, набор степеней вершин которой, мажорируются одной из следующих последовательностей: Некоторые параметры этого описания позднее были уточнены для отдельных классов 3-многогранников. Но вплоть до 2002 г. [10] ни один из этих параметров не был улучшен без ухудшения других ее параметров. В работе [10] О. В. Бородиным было получен следующий результат, усиливающий теорему Лебега. Теорема (Бородин, [10]). Каждый 3-многогранник содержит грань одного из следующих типов: Звездочкой помечены те вхождения, неулучшаемость которых была доказана, причем в каждом типе граней компоненты, предшествующие помеченным, также неулучшаемы. В [10] была поставлена задача: найти уточнение теоремы Лебега, не допускающее дальнейших усилений. Заметим, что решение этой задачи требует уточнения небольшого числа параметров. В диссертации сделан один шаг в этом направлении, а именно, член (4,5,17) заменяется на (4,5,16). Во второй главе представлены результаты о 2-дистанционной раскраске разреженных плоских графов. Раскраска вершин графа G называется 2-дистанционной, если любые две вершины, находящиеся друг от друга на расстоянии не более 2, получают разные цвета. Наименьшее число цветов в 2-дистанционной раскраске графа G называется 2-дис-танционным хроматическим числом графа G и обозначается через X2(G). Существует гипотеза Г. Вегнера (1977 г.) [36] о том, что Xi{G) JA(G)J +1 для любого плоского графа G с максимальной степенью A(G). Первый результат в этом направлении был получен Я. Ван-ден-Хойвелом и С. Мак Гиннессом [35], доказавшим что X2(G) 2Д + 25. В [9] О. В. Бородин, А. Н. Глебов, X. Брусма и Я. Ван-ден-Хойвел доказали, что для произвольных плоских графов Xi{G) [A(G)]+1 при A(G) 47, что улучшило оценку Г. Агнарсона и М.М. Холдорсона [11]: X2(G) LA(G)J+2 при A(G) 749. Для любого графа G с максимальной степенью А очевидной нижней оценкой для Х2 является А +1, так как А +1 есть необходимое число цветов для 2-ди станционной раскраски А-звезды, содержащейся в любом графе. В частности, эта оценка достигается на всех деревьях, но не достигается, например, на циклах С +\- Вопрос о том для сколь малых д (обхват графа) можно гарантировать равенство X2(G) — А + 1 путем наложения ограничения только на А был полностью решен в [37, 38]. В диссертацию включены только те результаты из работ [37, 38], которые были получены самим диссертантом.
Основным результатом является теорема 2.1, доказанная в разделе 2.2. Теорема 2.1. Пусть G — планарный граф, тогда X2(G) = А + 1 в каоїсдом из. следующих случаев: (i) А = 4 и g 15; (ii) А = 5 и g 13; (iii) А = б и g 12; (iv) А 7 и g Z 11; (v) А 9 и g = 10; (vi) А 16 и g = 9; (vii) А 30 ид = 7. В [38] было показано существование плоских графов с д 6, для которых Х2 А + 1 при произвольно большом Д. Таким образом, определенное нами условие на обхват, д 7, является неулучшаемым для 2-дистанционной (А 4- 1)-раскраши-ваемости плоского графа. Отметим, что доказательство утверждения (vii) в теореме Ввиду сказанного в предыдущем абзаце для обеспечения 2-дистанционной (Д + 1)-раскрашиваемости плоского графа G обхвата б потребовалось ввести дополнительное структурное требование: хотя бы один из концов каждого ребра графа G является вершиной степени 2. В [39] было доказано, что если G — плоский граф обхвата б, в котором A(G) 179, а каждое ребро инцидентно 2-вершине, то X2{G) = A(G) + 1. В диссертации этот результат был усилен следующим образом. Теорема 2.2. Если G — плоский граф обхвата 6, е котором A(G) 31, а каждое ребро инцидентно 2-вершине, то Xi{G) = A(G) + 1. Третья глава содержит результаты о (р, q)- и предписанной (р, д)-раскрасках плоских графов достаточно большого обхвата. Раскраска вершин графа G называется (р, д)-раскраской, если вершины графа G, расстояние между которыми равно 1, получают цвета, отличающиеся друг от друга не менее чем на р, а на расстоянии 2 — не менее чем на q. Если при этом для каждой вершины задан список допустимых цветов, то говорят о предписанной (р, д -раскраске. Наименьшее число цветов в (р, д)-раскраске графа G называется (р, « -хроматическим числом графа G и обозначается через Xp,q{G). Аналогично определяется предписанное (р, -хроматическое число Xlp,q{G)- Понятно, что ранее рассмотренная 2-дистанционная раскраска является в точности (1, 1)-раскраской. Для (р, р)-хроматического числа произвольного графа G имеем очевидную нижнюю оценку: XP,P(G) Ар + 1 (из тех же соображений, что и для (1,1)-раскраски). Заметим, что всегда Хр,р{@) Р Хід — V + 1 так как минимальную (1,1)-раскраску цветами 0,1,..., Хід—1 можно преобразовать умножением всех ее цветов нар в {р,р)-раскраску цветами 0,р,..., (хід — 1)р. Поэтому, ввиду теоремы 2.1, можно утверждать, что если G — плоский граф обхвата не меньше О. В. Бородин, А. Н. Глебов, X. Брусма и Я. Ван-ден-Хойвел [9] доказали для произвольного плоского графа G, что Xp,q{G) Юр + сь где С\ — величина, не зависящая от р.
Структурные свойства минимального контрпримера
Удалим перечеркнутое ребро и обесцветим его концы (см. рис. 1). Пусть d(w) Д-1 и d(v) Д—1. Покрасим один из концов ребра, например, у (на него действует не больше Д ограничений). Заметим, что х нельзя покрасить лишь в том случае, когда для х остается только цвет, занятый па у. В этом случае покрасим х в цвет вершины z, a z перекрасим в цвет вершины у (в дальнейшем такую операцию, встречающуюся уже в лемме 2, будем называть подкруткой). Через di(v) обозначим число всех непучковых цепей (ножек), а через dj(v) — число 1-цепей, ведущих в младшие вершины. Наконец, пусть ds(v) = b(v) + di(v) -— dj(v) — dq(v). Жесткими назовем все непучковые цепи, кроме 1-цепей, ведущих в младшие вершины, тогда их число равно di(v) — dj(v). Обозначим через dur(v) число неособых жестких ножек. Тогда, как легко видеть, ds(v) — b(v) + dur(v) + d(,(v). Пусть также k\(v) - число жестких неособых 1-цепей при вершине V. Лемма 4. Если вершина v является концом пучка толщины не менее б, то d[v) тіп{Д, Д + 1 - ДОКАЗАТЕЛЬСТВО. Пусть d(v) Д - kx(v) + dj(v) и d(v) А - 1. По лемме 3 имеем i(ti)) = Д. Удалим перечеркнутое ребро и обесцветим вершину v, смежные с v вершины, кроме лежащих на жестких 1-цепях, все 2-вершины пучка В, центральные вершины особых 3-цепей и младшие вершины, находящиеся на расстоянии 2 от v (см. рис. 2). Пусть t — толщина пучка В. Покрасим v в один из цветов, встречающихся па w или на оставшихся окрашенными вершинах, смежных с w. Таких цветов имеется Д - t + 1, а на выбор цвета для v имеется не более d(v) — t + ki(v) - dj(v) Д - t ограничений (поскольку неособые жесткие 1-цепи дают по 2 ограничении, тогда как остальные неособые цепи - одно ограничение, а две цепи каждой особой грани вместе дают два ограничения), т.е. v всегда можно покрасить в цвет вершины w или ее соседей. Затем красим смежные с w вершины из В (на последнюю имеется Д ограничений, так как цвет вершины v при пей встречается дважды); затем красим смежные с v вершины (что возможно, так как t б и d(v) Д-1; последней красится вершина у, и при этом, если нужно, делается подкрутка) и, наконец, центральные вершины особых 3-цепей и младшие вершины, находящиеся на расстоянии 2 от v. Лемма 5.
Если вершина v является концом пучка толщины не менее 6, то v инцидентна жесткой неособой 1-цепи либо непучковой 2-цепи. ДОКАЗАТЕЛЬСТВО. Удалим ребро uv одного из пучков В при v. Обесцветим v, псе смежные с ней вершины, кроме лежащих на особых 1-цепях, младшие концы 1-цепей и центральные вершины 3-цепей. Пусть конец пучка В, отличный от v, окрашен в цвет 1. Если вершину v можно покрасить в цвет 1, то раскраску можно продолжить следующим образом: раскрасим сначала непучковые вершины, смежные с v. а потом 2-вершины в пучках. Вершину и красим последней из пучковых; если нужно, применяем подкрутку. Последними красим младшие вершины и центральные вершины 3-цепей. Если v нельзя покрасить в цвет 1, то этот цвет встречается на вершине, находящейся либо на расстоянии 1 от v (на особой 1-цепи), либо на расстоянии 2. Если цвет 1 встречается на расстоянии 1 от v, то сначала красим v (это возможно, так как v имеет не более Д запретов, учитывая то, что каждая цепь, кроме особой 1-цепи, дает не более 1 запрета, а две цепи особой грани вместе дают 2 запрета).
Далее действуем как выше (для и цвет 1 повторяется). Пусть цвет 1 встречается лишь на вершине, находящейся па расстоянии 2 от v. Если цвет 1 встречается на особой 1-цепи, то красим в 1 смежную с v вершину 3-цепи этой особой грани. Если же цвет 1 встречается на пучковой цепи (не входящей в В), то красим в цвет 1 смежную с v вершину любой другой цепи этого пучка. Далее красим v и остальные вершины как выше. Следствие 6. Если b(v) 1, то dur(v) 1. Лемма 7. В G нет цепи vzw, где d(v) 13, d(z) — 2, d(w) = 5, кроме случая d(v) = d(w) — 2, т. с. ДОКАЗАТЕЛЬСТВО. Сначала считаем, что d(v) — 2, тогда d(w) 3. Обесцвечиваем вершины w,v и z (см. рис. 3). Первой красим v; это можно сделать, так как на нее действует не более А ограничений. Далее красим z: имеется не более 13 + 4 ограничений, затем красим w (не более 10 ограничений). Если же d(v) 3 и d(w) 3, то действуем аналогично (на v действует не более 24 ограничений, а Д 24). Лемма 8. В G пет цикла, образованного особыми Ъ-цепями. ДОКАЗАТЕЛЬСТВО. Пусть к таких цепей aiXiyiZidi+i образуют цикл (1 і к, a ak+i = йі). Удалим ребро Х\у\ и раскрасим полученный граф. Обесцветим все 2-вершины нашего цикла; тогда для каждой из 2к вершин xifZi имеется по два допустимых цвета, поэтому задача их раскраски сводится к нахождению обычной (по 2-дистанционной) предписанной раскраски четного цикла, что нетрудно сделать. Затем красим все уі (у каждой из них имеется по четыре ограничения на выбор цвета). Введем понятие спонсора следующим образом. Рассмотрим граф, образованный особыми (т. е. инцидентными 6-граням) 3-цепями. В силу леммы 8 эти цепи образуют лес. Возьмем висячую вершину и назовем ее спонсором для центральной 2-вершины единственной инцидентной ей 3-цепи. Затем отбросим эту 3-цепь, получившую спонсора, и повторим процедуру. Поскольку мы рассматриваем граф без циклов, то висячая вершина всегда найдется. По построению каждая центральная 2-вершина особой 3-цепи получает спонсора, а каждая Д-вершииа будет служить спонсором не более чем для одной 3-цепи. Будем использовать следующие правила перераспределения зарядов: R1: (і) Любая вершина, инцидентная двум соседним fc-цеиям, к 2, получает заряд 1 от инцидентной этим цепям грани ранга не менее 8. (іі) Любая вершина, инцидентная соседним 1-цепи и к-цеии, к 2 получает заряд от инцидентной этим цепям грани ранга не менее 7. (ш) Любая вершина v, инцидентная соседним 1-цепям, концы которых являются младшими вершинами, получает заряд 1 от инцидентной этим цепям грани. (iv) Любая ;-грань /, к 8, отдает заряд 1 центральной вершине инцидентной ей 3-цепи. R2: (і) Любая вершина v с d(v) 3, являющаяся концом 1-цепи, отдает смежной с ней 2-вершине заряд 1. (іі) Любая вершина v с d(v) 3, инцидентная к-цеїт, к 2, отдает смежной с ней 2-вершине заряд 2. (ш) Любая центральная 2-вершина особой 3-цепи (инцидентной G-грапи) получает заряд 1 от своего спонсора. R3: Любая младшая вершина получает заряд 1 от другого конца инцидентной ей 1-цепи. Заряды вершины v и грани /, оставшиеся у них после применения правил R1-R3, обозначим через Мз( ) и /4з(/) соответственно.
Окончательное распределение зарядов и его следствия
Мы знаем, что b(v) 1 для каждой слабой вершины v. Один из пучков при v, имеющих наибольшую толщину, назовем донорским для вершины v, а его конец -донором вершины v. R4: Слабая вершина v получает заряд — (У) от своего донора по донорском}1 пучку. Заряды вершины v и грани /, оставшиеся у них после применения правил R1-R4. обозначим через fj. (v) и Д (/) соответственно. Ясно, что /i (f) = /Лч(/) для .любой грани /, a /л (г ) Мз( ) лишь для слабых вершин и допоров. Далее в этом разделе мы убедимся, в частности, что никакой донор не является слабой вершиной, т. е. по любому донорскому пучку передача зарядов происходит лишь в одном направлении, откуда следует, что fi (v) = 0 для любой слабой вершимы v. Более того, будет показано, что окончательный заряд /Г(и ) любого донора, w неотрицателен. Доказательство того, что донорская вершина делает по меньшей мере одну передачу на однопучковую вершину. Пусть В - пучок толщины t с концами Vi и VR, где vi - одпопучковая слабая вершина. Докажем, что тогда Дз(зд) -Мз( ь) 0 и В - единственный донорский пучок при ид. Отсюда будет следовать, что окончательный заряд / ( ;к) вершимы VR положителен. Удалим одно ребро из пучка В и обесцветим вершины t i, v!{, все смежные с ними вершины, кроме тех, которые лежат на инцидентных им жестких 1-цемях, младшие вершины, находящиеся на расстоянии 2 от Vi и гід, а также все центральные вершины особых 3-цепей при vi и VR. Тогда па выбор цвета для vi имеется не более d{vi) — t + k\{vi) — dj(vi) ограничений, поскольку из d{vi) цепей при вершине г /, не несут запретов t + dj(vi) цепей, неособые жесткие 1-цепи несут по 2 запрета, а каждая особая 1-цепь вместе с соответствующей особой 3-цепыо песет в сумме 2 запрета, а все остальные цепи - не более чем по 1 запрету. Поскольку 6() = 1, то t = d(vL) -dur{vL) -2dq(vL) -dj(vL), откуда следует, что d(vL) t + h() -dj(vL) = = dur{vi) + ki(vi) + 2dq{vi) 2dur{yL,) + 2dq{vi) 10. В последнем неравенстве мы использовали то, что dur(v) + dq(v) 5 для любой слабой вершины v, так как M(v) 6. Если найдется цвет, в который можно покрасить и vi, и VR, то вершины графа G можно докрасить так, как в доказательстве леммы 5.
Поэтому можно считать, что VR имеет не менее Д +1 -10 22 ограничений на выбор цвета. Но по лемме 11 имеем Д — 13, откуда следует, что при гід существует не более 13 цепей, не входящих в пучок В. Если бы не более 8 из них давали бы по 2 запрета, то всего запретов было бы не более 2х 8 + (13 — 8) 22. Следовательно, при VR существует не менее 9 жестких к неособых 1-цепей (запреты от особых 1-цепей мы учитываем вместе с особыми 3- цепями), дающих по 2 запрета. Отметим, что тогда d3(vn) 1 + 9 + 1 = 11. Действительно, если кроме пучка В и 9 жестких неособых 1-цепей при у1{ не было бы ни пучковых, ни жестких пепучковых цепей, то число запретов для 1 ц не превосходило бы 2x9. Итак, Дз(ид) 11 - б = 4. Отметим, что VR делает передачу зарядов лишь по пучку В, поскольку толщина второго пучка, если он существует, не превосходит 13 - 9 = 4, а передачи происходят лишь по пучкам толщины пе менее 6 ввиду леммы 12. Остается отметить, что Дз(иь) —4, так как dUT{vi) 1 и b{vi) = 1, т.е. ds(vL) Ї 2. Доказательство того, что донорская вершина w делает передачи только на неоднопучковые вершины. Сначала докажем лемму о донорском пучке. Напомним, что кЛ(у) есть число жестких неособых 1-цепей при вершине v, и пусть d i(v) - число 3-цепей при v. По ложим do(v) = Д — d(v) + d3(v) + dj(v). Лемма 13.
Пусть слабая вершина vi с b(vi) 2 является концом донорского пучка В толщины t, где t б, с донорской вершиной VR, а p(vi) = t — ki(vi) + do{vL)-Тогда KI(VB) t + do(vx), если выполнено хотя бы одно из условий: 3 и при VR имеется хотя бы одна к-цепь, к 2, не входящая в В; перечеркнутое ребро и обесцветим vi, VR и все вершины смежные с ними по /„ -цепям, к 2,ч 1-цепям, ведущим в младшие вершины, а также все младшие па расстоянии 2 ОТ Vi И VR И Центральные ВерШИНЫ 3-ЦепеЙ, ИНЦИДеПТПЫХ Vi и VR (см. рис. 4). Будем считать, что конец второго пучка В , инцидентного vL, окрашен в цвет 1. Если цвет 1 не встречается ни на одной из смежных с VL вершин, то покрасим в цвет 1 одну из вершин, смежных с VL В пучке В. Теперь покрасим VR В цвет, отличный от 1: это возможно, так как VR имеет не менее t — 1 цепей пучка В и (I- VR) + CIJ(VR) непучковых цепей, не дающих ограничений на выбор цвета для VR, а /І:І(Ї Л) ножек дают по 2 ограничения, т. е. VR имеет не менее А + 1 — d(vR.) + d3(v) + dj(v) +1 - 1 -- &І(УД) = (IO{VR) + t- ki(vR) 1 свободных цветов. + dj(vL) - ki(vL) - t - ki{vL) + Д - d(vL) + d-s(vL) + dj(vL) = ( допустимых цистой (не менее t — 1 цепей пучка В не дают ограничений, как и Д — (i(t /J фантомных (отсутствующих) цепей, 3-цепей и мягких ножек, в то время как k[(vi) жестких неособых 1-цепей дают по 2 ограничения, а остальные — не более чем по одному ограничению). Обозначим эти р цветов через а\,..., ар. СЛУЧАЙ 1. На смежных с VR вершинах или на самой VR встречается хотя бы один из цветов Красим vi в этот цвет а, затем красим вершины, смежные с VR по ножкам (заметим, что в момент окраски вершины у от младшей смежной вершины добавляется не более четырех ограничений, по неокрашенных братьев из В у вершины у больше, так как t 6), потом пучковые вершины не из В, а потом все пучковые; из В, смежные с VR (ввиду повторения цвета а на последнюю вершину действует не более Д ограничений, если цвет 1 встречается на одной из смежных с vL вершинах не из В; если в цвет 1 покрашена смежная с ы вершина из В, то применяем подкрутку, введенную в доказательстве леммы 3). Далее по той же схеме красим соседей вершины VL; заметим только, что последними красим вершины из В , пользуясь тем, что для них цвет 1 повторяется, и применяя к самой последней подкрутку. Наконец, красим центральные вершины 3-цепей, а затем младшие вершины, на которые действуют не более 10 ограничений.
Доказательство результатов о предписанной (р, #)-раскраске
Пусть С — произвольный цикл нечетной длины. Добавим к каждой вершине этого цикла Д — 2 смежные с ней висячие вершины и обозначим построенный граф fc через (7. Рассмотрим произвольную (р, д)-раскраску вершин графа G u ,\ ,v/ цветов 0 - -)Хр,9 - 1- Предположим, что среди всех вершин цикла С пет вершины, цвет которой отстоял бы от концов заданного диапазона не менее чем па р. Тогда все вершины С окрашены в цвета, либо не превышающие р— 1 (назовем их младшими), либо не меньше ХРЛ - V (старшими). Поскольку две смежные вершины цикла не могут быть одновременно окрашены в младшие или старшие цвета, то па вершинах С происходит чередование младших и старших цветов.
Это противоречит нечетности цикла С. Допустим теперь, что v — вершина на С, цвет «о которой отстоит от обоих концов рассматриваемого диапазона цветов не менее чем нар, т. е. выполняются неравенства Р «о Xp,q Р 1- Рассмотрим множество цветов, использованных па. и и смежных с ней вершинах. Пусть цвета, использованные при раскраске вершин, смежных с v, суть a_t, ...,а_2,а-і,а!і,а2,...,ад-і, где a_t ... а_і а0 «і ... «д-(. Сначала предположим, что 0 і Д, т. е. цвета вершин, смежных с v, лежат но обе стороны от ао- Тогда выполняются следующие неравенства: Отсюда следует, что а_і — a_f (t — \)q и огд_( — а і (Д - і - 1)(/. Легко увидеть, что ctA - ot- т. с. количество использованных цветов на v и на смежных с ней вершинах не меньше 2р+1 + (Д—2) у цветов. Пусть теперь t = О либо t — Д, например, = 0. Тогда «о Р, «і _ «о р и Qfi+i -OL{ q при 1 г Д — 1. Поэтому сед 2р + (Д - \)q 2р + 1 + (Д - 2)q. Таким образом, в обоих случаях Xp,qifl) 2р + 1 + (Д — 2)q. Предложение 3.2 доказано. Рассмотрим полный двудольный граф G = G(U,W) = А Пі(п(о _і))«. Зададим предписание L(v) на каждой вершине графа G следующим образом. На 7-й вершине из U положим Цуі) = {(г-1)(п + 1)(2р-1)+р, (z-l)(n + l)(2p-l)+p + l,...,(i(n + + 1)- 1)(2р -1)+/)-1}.
Отметим, что любые два цвета из предписаний разных вершин из U отличаются не менее чем на 2р. С другой стороны, число вершин в W ровно столько, сколько существует способов выбора по одному цвету из предписания каждой вершины из U. Для цвета а положим Т(о) = {а—р+1,а—р+2,..., а+р— 1}. Ясно, что если «І Є L(vi), а,- Є L(VJ), где і ф j, то Т(а;) П T(ctj) = 0. Каждому способу выбрать по представителю а из предписания L(vi), где г ; є U, мы сопоставим вершину w Є W, па которой зададим предписание L(w) равным UKK» Д0 )- Из сказанного следует, что \L(w)\ = пТ(а ) = п(2р — 1). Из построенного предписания графа G невозможно выделить раскраску, поскольку как бы мы ни раскрасили вершины Vi,V2,...,vn из U в цвета с\\, а-2,..., а„ соответственно, найдется вершина w из W такая, что любой цвет /і из L(w) конфликтует с одной из вершин из U, а именно с той vu для которой /З Є Т(С\І). Предложение .13 доказано. Доказательство теоремы 3.4. Пусть G — наименьший по числу ребер граф со свойствами: Д(б ) А, где Д 4, 9(G) 5(Г(д- понимается цепь, состоящая из в точности к вершин степени 2. Допустим противное, т. е. в G нет /с-цепей, где к Г(д-2)(2г-і)1 +4, и минимальная степень графа не меньше 2. Стягивая каждую А цепь графа G в ребро, мы получаем планарный граф G с минимальной степенью не менее 3. Тогда в G есть грань ранга не больше 5. Следовательно, в графе G должна быть грань ранга не более 5(Г(д-2)(2Іг-і)1 + 4) чт0 противоречит условию д 5([(д_22 _1)] +4) + 1. Щ Предположим сначала, что в G есть висячая вершина v. Тогда- в силу мини- мальности графа G граф, полученный в результате удаления ребра, инцидентного v, имеет предписанную (р, д,)-раскраску вершин в 2р+ (Д — l)(2q — 1) цветов. Обесцветим v и продолжим данную раскраску на G. На цвет вершины v имеется 2р - 1 ограничений от смежной вершины и 2q — 1 ограничений от каждой вершины, находящейся на расстоянии 2 от v. Поэтому всегда найдется хотя бы один свободный цвет, в который можно окрасить вершину V. Заметим, что если из цени Р удалить любое ребро i ;u,+i, то можно последовательно раскрасить как левую часть Pi = V\...Vi цепи Р, так и ее прааую часть PR = Ш:--- +11 просто потому, что число цветов, разрешенных для очередной вер- шины, больше общего числа запретов от двух ее ближайших соседей (2р — 1 и 2(/- 1). Но, разумеется, возникает проблема стыковки при восстановлении ребра t ;ui+1. Сначала мы будем красить вершины цепи слева направо, v\, v%,..., подбирая место стыковки (vs, vs+i) и создавая для нее благоприятные предпосылки. Затем будем красить вершины цепи справа налево до ws+i и произведем стыковку. ШАГ 1. Раскраска цепи Р слева направо. Тенью Та цвета а назовем множество из 2р— 1 цветов, отличающихся от а менее чем на р. Заметим, что на вершину v\ действует 2р— 1 запретов от г () (составляющих Тп), а также 2д— 1 запретов от вершины и. Поэтому на V\ остается не менее (Д - 2)(2г/ -— 1) + 1 = с + 1 2 цветов; здесь мы полагаем с = (Д - 2)(2q — 1). Наибольший и наименьший из оставшихся на v\ цветов обозначим через t\ и Ь\ соответственно. Ясно, что г\ — t\ — b\ с . . Предположим, что вершины VQ, VI, .., Vj-i уже окрашены, а им ь\ есть два цвета, U (верхний) и bi (нижний), где U ЬІ, не противоречащие цветам предшествующих двух вершин. Величину ТІ — и — bi назовем разбросом. Редуцированным предписанием L (vi+i) вершины Vi+\ назовем множество цветов из L(vi+\), не запрещаемых вершиной v i. Замечание 1. Если L (vi+i) лежит по обе стороны от Tti или от г1\, например от Tti, то в L (vi+x) есть два цвета j+1 и 6j+i с разбросом не меньше. 2р — 1. Тогда мы красим Vi в ti и объявляем местом стыковки ребро Vi+\Vi+- (полагая, s — г + 1). Обращаем внимание на то, что тени, отбрасываемые цветами fi+1 и Ьі+і на вершину Vj+2, не пересекаются (если бы пересекались, то разброс на гі;+1 был бы меньше 2(р — 1) 2р — 1). Поэтому при любом цвете на vi+2, полученном при раскраске цепи Р справа налево и не противоречащем цвету вершины, Vi, миоісно раскрасить vi+i в один из цветов ti+\ и bi+\. Редуцированное предписание L (vi+{) имеет тип 1, если L (vi+i) (Z Tti U71(, и тип 2, если L (vi+i) С T UT . Ключевую роль в доказательстве теоремы 3.4 играет следующее
