Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Раскраска графов. 2

Министерство образования и науки Российской Федерации

ФГБОУ ВПО «Ишимский государственный педагогический институт

им. П.П.Ершова»

Кафедра математики, информатики и методики их преподавания

РАСКРАСКА ГРАФОВ

Курсовая работа

Исполнитель:

Игнатьева Валентина Сергеевна

студентка 3 курса дневного отделения

физико-математического факультета

Научный руководитель: ассистент

Теплова Валентина Давыдовна

Ишим 2012

Оглавление

Введение

Актуальность. Попытки решить сформулированную в середине 19 века задачу четырех красок привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Многие результаты середины 19 века, относящиеся к теории графов, были получены при решении практических проблем. В 20 веке задачи, связанные с графами, начали возникать не только в физике, электротехнике, химии, биологии, экономике, социологии и т.д., но и внутри математики, в таких ее разделах, как алгебра, топология, теория вероятностей, теория чисел и др. Методы этих разделов стали успешно использоваться для решения задач теории графов.

Наряду с термином граф в начале 20 века употреблялись в качестве синонимов и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт.

В проблематике теории графов можно выделить направления, носящие более комбинаторный или более геометрический характер. К комбинаторным относятся, например, задачи о построении графов с заданными свойствами, задачи о подсчете и перечислении графов с фиксированными свойствами. Геометрический (топологический) характер носят, например, задачи, связанные с обходами графа, и задачи, возникающие при укладке графа на различных поверхностях. Наряду с проблемами, носящими общий математический характер, в теории графов имеются специфические задачи. Например, изучаются различные свойства связности графа, исследуется строение графа по свойствам связности. При анализе надежности сетей связи, электронных схем, коммуникационных сетей возникает задача о нахождении количеств непересекающихся цепей, соединяющих различные вершины графа. Курсовая работа состоит из трех параграфов. В первом параграфе рассматриваются базовые понятия теории графов, во втором – понятие хроматического числа и хроматического многочлена и в третьем – гипотеза четырёх красок.

Цель курсовой работы – изучить основные понятия теории раскрашивания плоских графов и проанализировать известные результаты о гипотезе четырех красок. Достижению данной цели курсовой работы были поставлены и решены следующие задачи:

изучить такие основополагающие понятия теории графов, как граф, маршрут и контур, раскраска и плоский граф;
раскрыть понятие хроматического числа и хроматического многочлена графа;
изучить достаточные условия раскраски графов и проанализировать известные результаты о гипотезе четырех красок.

Объект – плоский граф.

Предмет – условия раскраски графов и его практическое применение.

Структура работы: работа состоит из введения, трех параграфов, заключения, списка использованной литературы и приложения.

§1. Введение в теорию графов

Рассмотрим сначала рисунок 1.1. и 1.2. на которых изображены соответственно участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображённой на рисунке 1.3.

Точки P,Q,R,S,T называются вершинами, линии называются рёбрами, а вся диаграмма называется графом. (Заметим, что точка пересечения линий PS и QT не относятся к вершинам графа, так как она не является ни общей точкой двух проводов, ни перекрёстком дорог).

Степенью вершины называется число рёбер, концом которых является эта вершина; на рисунке 1.2. это соответствует числу дорог, сходящихся у перекрёстка; так, степень вершины Q равна 4.

Очевидно, что граф, изображённый на рисунке 1.3, может описывать и другие ситуации. Например, если обозначить через P,Q,R,S,T футбольные команды, то наличие ребра между двумя вершинами можно трактовать как состоявшуюся встречу соответствующих двух команд (так согласно рис. 1.3, команда P уже сыграла с S, но ещё не сыграла с R); в этом случае степенью вершины будет число матчей, сыгранных соответствующей командой.

Рассмотренные выше ситуации можно описать и другим графом, изображённым на рис 1.4. Здесь мы устранили

рис. 1.1 рис. 1.2

рис. 1.3 рис. 1.4

“пересечение” линий PS и QT, проведя линию PS вне прямоугольника PQST. Заметим, что полученный при этом граф по-прежнему даёт нам представление о том, как соединены провода в электрической цепи, есть ли прямая дорога от одного перекрёстка к другому и какие футбольные команды встречались друг с другом; потеряна только информация, касающаяся “метрических” свойств (длина дороги, прямолинейность провода и т.д.) их соединения и что для наших целей метрические свойства несущественны. Исходя из этого, любые два графа, которые представляют одну и ту же ситуацию (как, например, графы, изображённые на рисунке 1.3 и 1.4.) будут считаться по существу одинаковыми. Более точно, мы будем говорить, что два графа изоморфны, если существует взаимно однозначное соответствие между их вершинами, обладающее тем свойством, что две вершины соединены ребром в одном графе тогда и только тогда, когда соответствующие им вершины соединены ребром в другом. На рисунке 1.5. изображён ещё один граф, изоморфный двум предыдущим. Заметим, что в графе представления о пространстве и расстояниях совершенно искажены, хотя, как и раньше, можно сразу сказать, какие точки соединены проводом или дорогой.

Стоит отметить, что граф, о котором шла речь до сих пор, “простой” в том смысле, что в нём любую пару вершин соединяет не более чем одно ребро. Предположим теперь, что дороги от Q до S и S до T (рис. 1.5.) слишком загружены и для их разгрузки проложены параллельные дороги, соединяющие те же точки; тогда соответствующая диаграмма будет выглядеть, как на рисунке 1.6. (Рёбра, соединяющие Q c S или S c T, называются кратными.) Если к тому же мы хотим построить гараж в пункте P, то на диаграмме это можно отметить ребром, идущим из P в P; такое ребро обычно называют петлёй (рис. 1.7).

А что получится, если по каждой из дорог, возможно, только одностороннее движение? Задавшись таким вопросом, мы придём к рассмотрению ориентированных графов (или, сокращённо, орграфов) Пример орграфа дан на рисунке 1.8; направления движения указаны стрелками (в этом конкретном случае в пункте Т творилось бы нечто несусветное, но это не помешает нам исследовать и такие ситуации). Заметим что если не все дороги односторонние, то можно получить соответствующий орграф, сопоставляя дороге с двусторонним движением два противоположно ориентированных ребра.

Много внимания уделяется в теории графов изучению различного рода цепей; под цепью понимается последовательность идущих друг за другом рёбер. Так, например, на рисунке 1.5 один из способов попасть из P в R описывается цепью P→Q→R длины 2; анологично, P→S→Q→T→S→R есть цепь длины 5. По очевидным соображениям цепь вида Q→S→T→Q нызывается циклом.

рис. 1.5 рис. 1.6

В общем случае не всегда можно найти цепь, связывающую две данные вершины ᴠ и ᴠᴠ рассматриваемого графа P R T Q S (см. рис.1.9);

рис. 1.7 рис. 1.8

такая цепь будет существовать, только если граф состоит как бы из одного куска. Для большей ясности рассмотрим пример графа, вершины которого соответствуют станциям лондонского и нью-йорского метрополитенов, а рёбра-линиям, соединяющим станции между собой. Совершенно очевидно, что по рёбрам этого граф невозможно попасть со станции Черинг Кросс в Лондоне на Гранд Централ Стейшн в Нью-Йорке.

С другой стороны, если рассматривать станции и линии только лондонского метро, то всегда найдётся путь, соединяющий две произвольно выбранные станции.

Граф,в котором любые две вершины соединины цепью, называется связным графом.

рис. 1.9

Дадим сначала определение простого графа G_w.

Пара (V(G), E(G)) называется простым графом, если V(G)- непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G)- конечное множество неупорядоченных пар различных элементов из V(G), называемых рёбрами (или линиями). Иногда V(G) называют множеством вершин, а E(G)-множеством рёбер графа G.

Например, на рисунке 1.10 изображён простой граф G, у которого множеством вершин V(G) является множество {u,v,w,z}, а множество рёбер E(G) состоит из пар {u,v}, {v,w}, {u ,w} и {w,z}. Говорят, что ребро {v, w} соединяет вершины v и w. Отметим, что, так как E(G) является множеством, а не совокупностью элементов, где некоторые элементы могут встречаться несколько раз; например, {a,b,c} – множество, тогда как {a,a,a,b,c,c} – семейство, то в простом графе данную пару вершин может соединять не более чем одно ребро.

Оказывается, многие результаты, полученные для простых графов, без труда можно перенести на более общие объекты, в которых две вершины могут быть соединены более чем одним ребром.

Кроме того, часто бывает удобно снять ограничение, состоящее в том, что ребро должно соединять две различные вершины, и допустить существование петель, т.е. рёбер, соединяющих вершину с ней самой.

рис. 1.10 рис. 1.11

Получающийся при этом объект в котором могут быть петли и кратные рёбра, называется общим графом, или просто графом (рис. 1.11). Подчеркнём тот факт, что каждый простой граф является графом, но не каждый граф является простым графом.

Более точно, графом G называется пара (V(G), E(G)), где V(G) – непустое конечное множество элементов, называемых вершинами, а E(G) – конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых рёбрами. Заметим, что употребление слова “семейство” говорит о том, что допускаются кратные рёбра. Будем называть V(G) множеством вершин, а E(G) – семейством рёбер графа G; на рисунке 1.11, V(G) – это множество {u,v,w,z}, а E(G)- это семейство, состоящее из рёбер {u,v},{v,v},{v,v},{v,w},{v,w},{v,w},{u,w},{u,w} и {w,z}. О каждом ребре вида с собой.

Предметом изучения в теории графов являются также ориентированные графы (называемые орграфами или сетями; однако мы будем употреблять слово “сеть” в несколько ином смысле). Орграфом D называется пара (V(D), A(D)), где V(D) – непустое конечное множество элементов, называемых вершинами, а A(D) – конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w – вторым, называется дугой из v в w и обозначается (v,w). Заметим, что дуги (v,w) и (w,v) различны. На рисунке 1.12 изображён орграф, дугами которого являются (u ,v), ( v ,v), (v ,w), (v ,w), (w ,v), (w ,u) и (w,z); порядок вершин на дуге указан стрелкой.

рис. 1.12

Некоторые специалисты по теории графов называют графом то, что мы называли простым графом. Во многих случаях, и особенно в приложениях, под графом понимается орграф. Ещё хуже, иногда графом называют объект, который получается, если снять условие конечности множества вершин или семейства рёбер. (Если оба они бесконечны, мы называем соответствующий объект бесконечным графом). Следует подчеркнуть, что любое из перечисленных определений графа вполне допустимо, если только пользоваться им последовательно.

Прежде чем привести примеры некоторых важных типов графов, удобно дать несколько простых определений.

Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (т. е. ребро вида {v,w}); при этом вершины v и w называются инцидентными этим вершинам). Аналогично, два различных ребра графа G называются смежными, если они имеют, по крайней мере одну общую вершину. Степенью (или валентностью) вершины v графа G называется число рёбер, инцидентных v; степень вершины v обозначается через p(v). При вычислении степени вершины v договоримся учитывать петлю в v два раза, а не один (если только явно не сказано иное). Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей (или концевой) вершиной. Так, граф, изображённый на рисунке 1.11, имеет одну висячую вершину, одну вершину степени 3, одну – степени 6 и одну – степени 8. Легко видеть, что если сложить степени всех вершин графа, то получится чётное число – равное удвоенному числу рёбер, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный ещё двести лет назад Эйлеру, часто называется леммой о рукопожатиях. Из неё следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно чётно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Из леммы о рукопожатиях сразу следует, что в любом графе число вершин нечётной степени должно быть чётным.

Два графа G₁ и G₂ называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число рёбер, соединяющих любые две вершины в G₁ , равно числу рёбер, соединяющих соответствующие вершины в G₂. Так, два графа, изображённые на рисунке 1.14, изоморфны при соответствии u ↔ l, v ↔ m, w ↔ n, x ↔ p, y ↔ q, z ↔ r. Заметим, что эти графы имеют по шесть вершин – другие точки пересечения рёбер вершинами не являются. u₁ u₂ u₃ u₄

рис. 2.4

рис. 2.5

Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все рёбра принадлежат E(G). Так, граф на (рис. 1.10) является подграфом графа, изображённого на рисунке 1.13, но не является подграфом ни одного из графов, приведённых на рисунке 1.14 (так как последние не содержат “треугольников”).

Наконец, матрицей смежности графа G с множеством вершин {v₁,…,v_n} (соответствующей данной нумерации вершин) называется матрица A=(a_ij) размера n*n, в которой элемент a_ij равен числу рёбер в G, соединяющих v_i и v_j. Например, на рисунке 1.15 дана матрица смежности графа, изображённого на рисунке 1.13. Можно получить несколько различных матриц смежности данного графа, меняя обозначения его вершин; это приведёт к изменению порядка строк и столбцов матрицы А. Но в результате всегда получится симметричная матрица из неотрицательных чисел,

рис. 1.15

Обладающая тем свойством, что сумма чисел в любой строке или столбце равна степени соответствующей вершины (здесь каждая петля учитывается в степени вершины один раз). Обратно, по любой заданной симметричной матрице из неотрицательных чисел легко построить граф (единственный с точностью до изоморфизма), имеющий данную матрицу своей матрицей смежности. Отсюда следует, что теорию графов можно свести к изучению матриц особого типа.

§2. Понятие хроматического числа и хроматического многочлена графа

Пусть граф G не имеет петель; тогда G называется k-раскрашиваемым, если каждой его вершине можно приписать один k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета. Если граф G является k-раскрашиваемым, но не является (k-1)-раскрашиваемым, то назовём его k-хроматическим, а число k назовём храмотическим числом графа G и обозначим через χ(G). На (рис. 2.1) изображён 4-хроматический (и, следовательно, k-раскрашиваемый при k>=4) граф; цвета обозначены греческими буквами. Для удобства будем предпологать, что все рассматриваемые графы, не содержат петель; однако мы будем допускать существование кратных рёбер, так как они не влияют на наши рассуждения.

рис. 17.1

Ясно, что χ(K_n) = n, и, следовательно, легко построить графы со сколь угодно большим хроматическим числом. С другой стороны, нетрудно видеть, что χ(G) = 1 тогда и только тогда, когда G- вполне несвязный граф, и что χ(G)= 2 тогда и только тогда, когда G- двудольный граф, отличный от вполне несвязного графа.

При каких условиях граф является 3-хроматическим, неизвестно, хотя легко привести примеры таких графов; к ним относятся циклические графы с нечётным числом вершин, колёса с нечётным числом вершин, граф Петерсена. Колёса с чётным числом вершин являются 4-хроматическими.

О хроматическом числе произвольного графа мало что можно сказать. Если граф имеет n вершин, то очевидно, что его хроматическое число не превосходит n, а если граф содержит в качестве подграфа K_r, то его хроматическое число не меньше r, однако в таком запасе сведений далеко не уедешь. Значительного прогресса можно добиться, если известна степень каждой вершины графа.

ТЕОРЕМА 1. Если наибольшая из степеней вершин графа G равна p, то этот граф (p+1)-раскрашиваем.

Доказательство: Проведём индукцию по числу вершин в G – граф с вершинами; если из него удалить произвольную вершину v вместе с инцидентными ей рёбрами, то в оставшемся графе будет (n-1) вершин, причём степени вершин по-прежнему не превосходит p. По предложению индукции этот граф (p+1)-раскрашиваем; отсюда получится (p+1)-раскраска для G, если окрасить вершину v цветом, отличным от тех, которыми окрашены смежные с ней вершины (а их не более чем p).▼

ТЕОРЕМА 2: (Брукс 1941). Пусть наибольшая из степеней вершин графа G равна p. Тогда G является p-раскрашиваемым, за исключением тех случаев, когда (i) G содержит в качестве компоненты граф K_p+1 или (ii) p=2 и цикл нечётной длины является компонентой G.

§3. Гипотеза четырёх красок

Любое из следующих ниже условий, наложенных на карту, является достаточным для того, чтобы быть уверенным, что такая планарная карта раскрашивается в четыре цвета:

а) некоторая область ограничена не более чем четырьмя сторонами;

б) каждая область ограничена не более чем пятью сторонами;

в) имеется не более 21 вершины степени 3;

г) совокупность стран, у которых более четырех соседей, можно разделить на два класса так, что один класс содержит не более одной страны и никакие две страны другого класса не являются соседями;

д) карта — кубическая, не содержит мостов, и число сторон каждой области кратно трем. Однако очень мало предложено конструкций, способов, указывающих, как надо раскрашивать некоторые достаточно общие классы карт. Следующая схема продемонстрирует нам, каким образом можно раскрасить в три цвета ребра карты из одного такого класса. Пусть М — кубическая карта, не имеющая мостов. Предположим также, что число ребер на границе каждой области кратно трем, т. е. карта М удовлетворяет условию д). Рингель предложил конструктивную схему окрашивания ребер карты М в три цвета. Перенумеруем цвета 1, 2 и 3, которые циклически упорядочим: за 1 следует 2, за 2 — 3, за 3 — 1. Если е, f и g—три ребра карты М, сходящиеся в одной вершине, то упорядочим их по направлению часовой стрелки, условившись, что, двигаясь от ребра е по часовой стрелке, мы встретим сначала f и потом g.

Схема раскрашивания: Начнем с некоторого ребра е карты М и окрасим его в произвольный цвет, скажем, 1. Рассмотрим теперь четыре ребра, смежные с е, по два в каждом конце ребра е. Так как в обоих концах ребра е ребра упорядочены по часовой стрелке, то каждое из четырех ребер либо предшествует е, либо следует за ним. Припишем каждому из них соответствующий цвет. Таким образом, ребро f, следующее за е, окрашивается в цвет 2. Этот процесс продолжаем до тех пор, пока не будут окрашены все ребра. Эта процедура не двусмысленна, другими словами, каждое ребро окрашивается только в один цвет. Следовательно, никакие два смежных ребра не окрашиваются в одинаковый цвет. Этим обеспечивается конструктивное доказательство достаточности условия д) для раcкрашиваемости карты в четыре цвета, потому что, как мы уже видели, если задана трехцветная раскраска ребер кубической карты, не содержащей мостов, то существует способ раскрасить области этой карты в четыре цвета. Раскраска карт на поверхностях, отличающихся от плоскости и сферы.

На фоне того, что проблема четырех красок до сих пор не решена, может показаться неожиданным, что аналогичные задачи для других ориентируемых поверхностей решены полностью. Говорят, что поверхность Sp имеет род р, если она гомеоморфна сфере с р ручками.

рис .19

Сформулируем знаменитую теорему Хивуда о раскраске карт на таких поверхностях. Любая карта, расположенная на (ориентируемой) поверхности SP рода р (р=1, 2...), может быть раскрашена в число цветов, не превосходящее χ_p, где

Здесь, как и раньше, квадратные скобки означают целую часть числа, заключенного в них. Доказательство этой теоремы можно найти в книге Харари. Заметим, что χ_p=4, т. е. справедливость этой теоремы при р=0 была бы равнозначна справедливости гипотезы четырех красок. Но, к сожалению, единственное известное доказательство теоремы существенно зависит от предположения р>0. Хивуд, обнаруживший ошибку в доказательстве Кемпе, сам оказался в какой-то мере в роли Кемпе. А именно он считал, что ему удалось доказать, что число χ для р>=0 достигается хоть для одной карты на поверхности рода S_p, т. е. на поверхности S_p имеется карта, хроматическое число которой равно χ_р. Через год Хеффтер указал неточности в рассуждениях Хивуда и, помимо этого, доказал точность числа χ_p для 1<=р_B=6. В самое последнее время Рингелю и Янгсу удалось доказать для любого целого положительного р, что на поверхности рода р имеется карта, хроматическое число которой в точности равно χ_p.

Рассмотрим достаточность шести цветов.

ТЕОРЕМА 1: Любая планарная карта может быть раскрашена в шесть цветов.

Доказательство: Проводится индуктивно по числу областей. Если карта состоит не более чем из шести областей, то она, конечно, раскрашивается в шесть цветов. Предположим уже доказанным, что любая карта, состоящая из r областей, раскрашивается шестью цветами. Докажем теперь, что любая карта с r+1 областями обладает этим же свойством. Рассмотрим карту с r+1 областями. Как мы уже видели, вследствие формулы Эйлера хотя бы одна из областей имеет не более пяти сторон. Тогда, разделив эту область на части (рис. 3.1) и присоединив их к соседним областям, получим новую карту с r областями.

рис. 3.1 рис. 3.2

Эту карту можно по предположению индукции раскрасить в шесть цветов. Возвращаясь к исходной карте с r+1 областями и учитывая, что выделенная область имеет не более пяти соседей, получаем, что для этой области имеется «свободная» краска из числа шести. ▼

Рассмотрим достаточность пяти цветов.

ТЕОРЕМА 2 (теорема Хивуда): Любая планарная карта может быть раскрашена в пять цветов.

Доказательство: Проводится в терминах дуальных планарных графов индукцией по числу вершин r. Если r>=5 , то теорема очевидна. Предположение индукции заключается в том, что каждый планарный граф с r вершинами можно раскрасить в пять цветов. Пусть G— планарный граф с r+1 вершинами. В графе G имеется вершина v степени 5 или меньше. Граф G — v, получающийся из G удалением вершины v и инцидентных с ней ребер по предположению индукции можно раскрасить в пять цветов. Рассмотрим такую раскраску графа G— v. Цвета будем обозначать через C₁, C₂, C₃, C₄, C₅. Понятно, что если в раскраске вершин, смежных с v, хотя бы один цвет не используется, то его можно использовать для окрашивания вершины и, поэтому если, в частности, степень вершины v меньше пяти, то граф G раскрашивается в пять цветов. Пусть степень вершины v равна пяти, и для вершин графа G, смежных с v, при пятицветной раскраске графа G— v использованы все пять цветов. Пусть смежные вершины v1, v2, v3, v4, v5. окрашенные соответственно в цвета c1,с2,с3, с4, с8, циклически упорядочены (рис. 3.2) (это всегда можно сделать, занумеровав подходящим образом смежные вершины и перенумеровав, если нужно, цвета). Обозначим через G₁₃ подграф графа G— v, порожденный всеми вершинами, окрашенными в один из цветов с₁ и с₃. Этот граф может быть несвязным. Если вершины v₁ и v₃ принадлежат при этом разным компонентам, то граф G—v можно перекрасить в те же пять цветов, поменяв для этого в компоненте графа G13, содержащей v₁, друг с другом цвета вершин с₁ и с₃ (с₁ на с₃ и с₃ на с₁). И тогда для окраски вершины v высвобождается цвет с₁. Рассмотрим теперь случай, когда вершины v₁ и v₃ принадлежат одной компоненте G₁₃. Тогда в графе G— v имеется элементарная цепь, соединяющая v₁ с v₃, все вершины которой попеременно окрашены в с₁ и с₃. Эта цепь вместе с цепью v₃vv₁ образует в графе G элементарный цикл, который окружает либо вершину v₂, либо две вершины v₄ и v₅. В любом из этих случаев вершины v₂ и v₄ нельзя соединить цепью в графе G— и, вершины которой были бы окрашены попеременно в цвета с₂ и с₄. Поэтому рассматривая подграф G₂₄ графа G—v, порожденный всеми вершинами, окрашенными в цвета с₂ и с₄, заключаем, что вершины v₂ и v₄ принадлежат различным его компонентам. Меняя между собой цвета с₂ и с₄ вершин той компоненты подграфа G₂₄, которая содержит вершину v₂, выделяем «освободившийся» цвет с₂ для вершины v.▼

Однозначность раскрашивания: Каждая раскраска графа G в k цветов порождает разбиение множества его вершин на k одноцветных классов. Если любой другой раскраске в k цветов индуцированное разбиение на классы будет тем же, то говорят, что граф G однозначно раскрашивается в k цветов. Заметим, что при любой k-раскраске однозначно раскрашиваемого в k цветов графа каждая вершина v должна быть смежна хотя бы с одной вершиной каждого цвета, отличающегося от цвета вершины v. Иначе, перекрасив только одну вершину и, получили бы другую раскраску. Мы здесь приведем некоторые результаты относительно однозначности раскрашивания графа в k цветов.

ТЕОРЕМА 3: При k-раскраске однозначно раскрашиваемого графа в k цветов подграф, являющийся объединением любых двух одноцветных классов вершин, связен.

ТЕОРЕМА 4: Однозначно k-раскрашиваемый граф — (k—1)- связный. Соответствующий подграф из т одноцветных классов (2<=m<=k)–(m-1)- cвязный

ТЕОРЕМА 5: Для каждого k<=3 существует однозначно k-раскрашиваемый граф, не содержащий в качестве подграфа полный граф на k вершинах. Заметим, что здесь речь шла не только о планарных графах. Что касается планарных графов, то поскольку в каждом таком графе обязательно имеется хотя бы одна вершина не более чем с пятью смежными вершинами, планарный граф раскрашивается в k цветов при k>= 6 неоднозначно. Более того, не существует планарных графов, однозначно раскрашиваемых в пять цветов. Известно также, что каждый однозначно 4-раскрашнваемый планарный граф является максимальным планарным.

ТЕОРЕМА 6: Пусть G—3-хроматический планарный граф. Если в G содержится такой треугольник Т, что какую вершину v ни взять, существует последовательность треугольников Т₁,.... Т_m, в которой соседние два треугольника имеют общее ребро, и вершина v есть вершина последнего треугольника Т_m, то граф G раскрашивается в три цвета однозначно.

Однозначно раскрашиваемый в три цвета планарный граф, имеющий не менее четырех вершин, должен содержать по крайней мере два треугольника. В общем же случае раскрашивание карты или графа неоднозначно. Некоторые последние результаты, рассматриваемых в этой работе, осталась проблема раскраски бесконечных планарных графов, в связи с которой можно было бы упомянуть об исследованиях Эрдеша, Хэжнала, Хэймена. Можно определить несвязное раскрашивание (или D-раскрашивание) графа как разбиение множества вершин на подмножества V₁, V₂, ... V_n, такое, что для каждого i часть графа G, порожденная множеством V_i, несвязна. D-хроматическое число χ_d (G). аналогично хроматическому числу, есть наименьшее число подмножеств при любом D-раскрашивании графа G. D-хроматическое число обладает многими свойствами хроматического числа, но кое в чем есть различие. Например, доказана следующая теорема: если G —планарный граф, то X_d(G)>= 4 Несколько слов об эвристическом методе раскрашивания графа, разработанном Пеком и Уильямсом. Они рассматривают граф и предлагают выполнить для нахождения тех вершин, которые должны быть окрашены в k-й цвет, следующие операции: