Строение и раскраска плоских графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАЖ Сибирское отделение Институт математики

На правах рукописи

БОРОДИН Олег Вениаминович

УЖ 519.1?

СТРОЕНИЕ И РАСКРАСКА ПЛОСКИХ ГРА<ЮВ 01.01.09 - математическая кибернетика

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск - 1994

ГБ ОД

п !'"''< Г" ">

;; : .л v./.

Работа выполнена б Институте математики СО РАН

Официальные оппоненты: доктор физико-математических на

профессор Естигнеев Б.А

доктор физико-математических нг профессор Егорычев Г.П.

доктор физико-математических нг профессор Зыков A.A.

Ведущая организация: Вычислительный центр РАН

Зашита состоится " II " января 1995 г. в 16 час

на заседании специализированного совета Д 002.23.03 при Инст туте математики СО РАН (630090, Новосибирск, 90, Университе ский проспект, 4).

С диссертацией можно ознакомиться в библиотеке Институ математики СО РАН.

Автореферат разослан "_"_ 1994 г.

Ученый секретарь

Специализированного совета Д 002.23.03 доктор физико-математических наук А.В.Косточ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Строение плоских графов привлекает математиков начиная с открытия Эйлером знаменитой формулы В - Р + Г = 2 для многогранников. (Согласно теореме Штейница 1922 г., эйлеровы многогранники взаимно-однозначно соответствуют 3-связным плоским графам.) Уже Лежандру было известно [16, с. 273 о существовании в любом многограннике вершины и грани ранга не более 5, а также либо вершины ранга 3, лиоо грани ранга 3 (ранг - это число инцидентных ребер). Важную роль в изучении строения плоских графов общего вида сыграла теория эйлеровых вкладов, предложенная Лебегом в 1940 г. Оборотной стороной универсальности и простоты этого подхода является его недостаточная- разрешающая способность: легко получаются всевозможные приближенные оценки, но как правило не удается получить неулучшаемых структурных характеристик. В частности, более тонкие соображения потребовались Коцигу [14] для доказательства в 1955 г. теоремы о том, что минимальный вес ребра (сумма степеней концевых вершин) в многограннике не превосходит 13 (оценка точна). Но и после этого долгое время не удавалось ответить на многие естественные вопросы о строении плоских графов, поставленные Лебегом С18], Коцигом [14-16], Юцовичем [13], Грюнбаумом [10-12], Пламмером [20, 21] и другими. Часть этих задач решена в данной диссертации.

Большое число работ за последние сто лет было посвящено изучению плоских графов специального вида, а именно, класса Т5 плоских триангуляции с минимальной степенью 5. Дело в том, что фактически именно Т^ является объектом исследования в известной задаче о четырех красках, поставленной в 1654 г. Гатри. Полученное Аппелем и Хакеном в 1976 г. решение состояло в построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другими словами, был найден такой набор структурных фрагментов, что в любой триангуляции встречается хотя бы один из этих фрагментов, и в то же время ни один из фрагментов не может содержаться в минимальном контрпримере к теореме о четырех красках. Важным промежуточным пунктом в этих

исследованиях стала теорема Лебега 1940 г., описывающая строение окрестностей 5-вершины в Т . Б этом описании была еще очень слаба связь с 4-раскраской; многие конфигурации не являлись сводимыми. Далее Хееш разработал теорию того, как погружать имеющуюся систему конфигураций в более мощные системы конфигураций, сводимых по внешним признакам. Суть его подхода - в последовательной замене конфигураций, оказавшихся несводимыми, на серии объемлющих конфигураций с большими шансами быть сводимыми. В итоге программа Хееша и была реализована Аппелем и Хакеном в результате больших вычислений вручную и массированного применения ЭВМ.

Из приведенного примера видна роль структурных результатов в решении задач раскраски плоских графов.

Цель работы. В диссертации прослеживаются связи между задачами цикловой, совместной и предписанной раскраски и верхними оценками минимального веса ребра и грани для некоторых классов плоских графов. Полученные результаты являются, как правило, неулучшаемыми и позволяют ответить на ряд вопросов, поставленных в 60-70 гг. Рингелем, Коцигом, Грюнбаумом, Юцовичем, Пламмером, Кронком и другими.

Научная новизна. В диссертации получена новая довольно подробная информация о строении окрестностей ребра и грани в плоских графах. Ранее были известны в основном приближенные верхние и нижние оценки для ряда структурных характеристик, принадлежащие Вернике, Франклину, Лебегу, Ope, Коцигу, Грюн-Оауму, Плашеру, Юцовичу, Тофту и другим исследователям.

Обнаружена тесная связь между задачами- Рингеля о 6 красках и Оре и Плашера о цикловой раскраске (i960) с задачей о циклической связности Грюнбаума (1975) и оценками на вес грани в триангуляции Лебега ( 1940) и Коцига ( 1963, 1976).

Разработан подход, позволивший решать задачу о совместной раскраске вершин, ребер и граней Кронка и Митчема (1973), входящую под номером 1.10 в список Тофта [24], и задачу о предписанной раскраске ребер плоских графов на основе новых теорем коциговского типа о весе ребра.

Эти связи между старыми и казавшимися разрозненными

задачами и составляют идейную основу диссертации. Главные же технические трудности, преодоленные в работе, состояли в адаптации метода перераспределения вкладов к задачам о весе ребра и грани. До этого применялись лишь простые соображения, основанные на равномерном распределении вкладов (Лебег, Ope, Пламер, Гофт) и в лучшем случае учитывалась неповторяемость вершин степени не более 5 (младших) в окружении вершин (Франклин, Коциг, Юцович).-

Таким образом, ядром диссертации является блок преимущественно неулучшаемых результатов о строении окрестности ребра и грани в различных классах плоских графов и основанные на них оценки для цикловой, совместных и предписанной раскрасок. Этот материал содержится в главах 1 и 2. Ряд новых результатов о строении и раскраске графов, уложенных на плоскости и других поверхностях, приводится в главе 3.

Среди результатов диссертации центральное место занимает

(а) решение задачи Рингеля' (1965 г.) о 6 красках [26]. Теорема о 6 красках, допуская формулировку в терминах 1-вложимости (теорема 2.1), цикловых (теорема 2.1') и совместных раскрасок (теорема 2.1.."), подтолкнула исследования во всех трех направлениях. Как раз накануне решения задачи Рингеля. Бодендик, Вагнер и Шумахер [7] опубликовали в общематематическом журнале статью с • призывом к молодому поколению математиков заняться ею. Вскоре Бодендик [ô] опубликовал там же сообщение о том, что задача решена диссертантом. Этот результат уже успел войти в обзоры и упоминается Харбортом в,предисловии к книге, посвященной 70-летию Рингеля. Вскоре в Журнале теории графов (США) выйдет найденное диссертантом новое доказательство теоремы о 6 красках.

Другими основными результатами диссертации являются:

(б) подтверждение (за несколькими исключениями) предположения xvef s Д + 4 Кронка и Митчема (1973 г.) о совместной раскраске

'вершн, ребер и граней (теорема 2.6) и установление (за несколько большим числом исключений) неулучшаемой оценки л: < < Д + 2 (теорема 2.7), где Д - максимальная степень графа;

(Б) блок теорем коциговского типа о весе ребра (теоремы 1.5-1. 12);

(г) одновременное решение задач Грюнбаума (1975 г.) о циклической связности и Коцига (1963 г.) о весе грани в триангуляции (теорема 1.16);

(д) решение серии задач Грюнбаума (1973 г.) и Юцовича (1974г.) о числе "легких" ребер (теоремы 1.20-1.23);

(е) точная верхняя оценка хроматического числа графов, 1-вло-жимых в псевдоплоскость в смысле Кайнена (теорема 3.2);

(ж) теорема о диагональном преобразовании триангуляция ориентируемых поверхностей (теоремы 3.3 и 3.4).

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

Апробация. Результаты диссертации докладывались на Совещании по теории графов в Самаркандском госуниверситете (1963); VII (Иркутск, 1965) и VIII (Горький, 1966) Всесоюзных конференциях по теоретической кибернетике; I, II и III Всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1964, 1967, 1990); Всесоюзной школе по теории графов и ее приложениям (Новосибирск, 1966); Первом Всемирном конгрессе общества математической статистики и теории вероятностей им. Бернулли (Ташкент, 1966); ь лекциях XXX Семестра по комбинаторике и теории графов Международного математического центра им.Банаха (Варшава, 1967); в пленарных докладах на IV Чехословацком международном симпозиуме по комбинаторике (Пра-хатице, ЧСФР, 1990) и Международных конференциях: "Дискретная

математика" (Айзенах, Германия, 1990), по теории графов памяти Юлиуса Петерсена (Хиндсглавль, Дания, 1990) и "Миноры графов" (Сиэтл, США, 1991) и Ежегодном собрании Германского математического общества (Дуйсбург, 1994), а также на научно-исследовательских семинарах Института математики СО РАН, Математического института Венгерской АН (Будапешт), университетов Оденсе (Дания), Нэшвила (США), Лондона, Рединга, Ноттингема и Оксфорда (все - Англия), Дрездена, Иены, Фрайберга, Ростока и Ильменау (все - Германия).

Публикация. Основные результзаты диссертации опубликованы в [26-563. Большинство из результатов по раскраске включено в внигу Б.Тофта и Т.йенсена (Дания) "Задачи раскраски графов", выходящую в Wiley (США). За эти работы получены премии на конкурсах Института математики в 1967, 69 и 92 гг.

Структура и объем работы. Диссертация изложена на 239 страницах, состоит из введения, трех глав и списка литературы (110 наименований).

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении излагается предыстория, обсуждаются результаты диссертации и даются необходимые определения и обозначения.

В главе 1 изучается локальное строение плоских графов. В § 1.1. получено дуально-симметричное усиление теоремы Лебега [16] об инцидентности младших вершин и младших граней. Через б обозначается минимальная степень вершины в графе. (Аргументы функций по возможности опускаются.) Ранг вершины часто называют степенью. Вершины и грани ранга i иногда называются для краткости i-вершинами и ¿-гранями.

ТЕОРЕМА 1.1. В плоском графе с <5 > 3 есть либо 5-вершина, инцидентная четырем 3-граням, либо 4-вершина, инцидентная 3-грани, либо 3-вершина, инцидентная 3- или 4-грани, либо, наконец, 5-грань, инцидентная четырем 3-вершинам.

Коциг [14] доказал, что в любом многограннике найдется ребро с суммой степеней концевых вершин (весом) не более 13,

причем оценка достишма. Некоторое время оставался открытым вопрос Эрдеша СИ, с. 454] о возможности распространения этой теоремы на все плоские графы с д г 3. Утвердительный ответ был анонсирован Барнетом СИ, с. 468] и независимо получен диссертантом [43] в интересах приложений к раскраске. В § 1.2 приводятся верхние оценки на минимальный вес ребра, ш, в нескольких классах плоских графов.

Пример полного двудольного графа Кз п показывает, что

если <5 < 3, то щ не ограничен сверху. В следующих двух случаях, несмотря на присутствие 2-вершин, верхняя оценка для и существует. Определим /с-пучок как индуцированный подграф на к + 2 вершинах, в котором выделены две вершины, а каждая из остальных к вершин смежна только с выделенными.

ТЕОРЕМА 1.5. Если в плоском графе 5 > 2 и нет к-пучков, где к г 2, то V) £ 5к + 7, причем оценка неулучшаема.

Цикл Си и ...и называется 1-чередующимся, если вершины V ,и.....V , имеют степень I. Ясно, что 2-пучок есть част-

13 гк-1 *

ный случай 2-чередующ.егося цикла.

ТЕОРЕМА 1.6. Если в плоском графе <5 > 2 и нет 2-череду-ющихся циклов, то и £ 15, причем оценка неулучшаема.

Коциг [14] доказал, что если а > 4, то ь> < И, причем оценка достижима. Оказывается, она имеет место и в более широком классе графов, полезном с точки зрения раскраски.

ТЕОРЕМА 1.7. Если в плоском графе 5 > 3 и нет 3-череду-ющихся 4-циклов, то м 5 11 (оценка неулучшаема).

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

ТЕОРЕМА 1.9. Пусть в плоском графе & (а) б > 2;

(б) нет утопленных 2-вершин;

(в) нет полуутопленных 2-вершин, инцидентных 6-грани;

(г) нет 2-вершин, смежных с младшими вершинами;

(д) нет 4-цикла Си^гм^]. в котором каждая из V и ьа либо утопленная 2-вершина, либо полуутопленная 3-вершина. Тогда в О есть полуутопленное ребро веса не более 11.

Лебег [16], уточняя известный еще Лежандру факт, что при а > 3 в плоском графе есть младшая грань, доказал, что имеется либо 3-грань, инцидентная ребру, степени концевых вершин которого мажорируются одной из пар (3,го), (4,11) и (5,7), либо 4-грань, инцидентная ребру типа (3,5), либо 5-грань,инцидентная (3.3)-ребру. Заметим, что отсюда не следует ограниченность ш, доказанная лишь в 1955 г. Коцигом [14]. Принципиальная возможность совмещения теорем Лебега и Коцига показана диссертантом в [36]. В диссертации этот вопрос решен полностью.

ТЕОРЕМА 1.5. В плоском графе с д > 3 есть либо 3-грань инцидентная ребру, мажорируемому одной из пар (3, 10). (4, 7) или (5, 6), либо 4-грань, инцидентная (3, 5)-ребру, либо 5-грань, инцидентная (3, 3)-ребру; все пять мажорирующих пар достижимы, причем независимо друг от друга.

Ребро называется слабым и полуслабым, если оно соответственно инцидентно двум или хотя бы одной 3-грани. Минимальный вес слабых и полуслабых ребер обозначается через м** и и*. Очевидно, что а** > и* > ы. Еще Лебегу [163 было известно, что при б г 3, если ь>* = со, то V) < б, причем оценка неулучшаема. В [41] диссертант, в интересах приложений к раскраске, доказал следующее усиление теоремы Коцига [143: если в плоском графе 5 > 3, то либо и**< 13, либо «*< 12, либо ы < 11. Завершающей в данном направлении является

ТЕОРЕМА 1.10. Если граф плоский с б > 3, то либо ь>**< 13, либо ъ>* < 10, либо у < 8, причем все границы достижимы независимо друг от друга.

Для подтверждения достижимости второй оценки построен граф с параметрами: ¡/* = 14, и* = 10 и ъ> = 9. Следующие факты в сопоставлении с предыдущей теоремой служат одной из иллюстраций причудливости строения плоских графов,которое,по-видимому,

не допускает сколько-нибудь компактного описания.

ТЕОРЕМА 1.11. Если плоский граф с б > 3 имеет ш**= а>, то либо ю* < 9. либо и £ б, причем границы достижимы независимо друг от друга.

Построен граф с параметрам-!: ¡/* = <*>, щ* = ы = 9. С другой стороны, если лишь несколько усилить условие ш**= со, то уже щ < 8, что обобщает теорему Лебега [16] о том, что из щ* = со следует ы £ в.

ТЕОРЕМА 1.12. Если в плоском графе б > 3,а границы 3-гра-ней не пересекаются, то ш < 6.

Неулучшаемость теоремы следует из того же графа с ш**= со и ¡/ = ь> = 8. Вернике [25] для б = 3, а Коциг [14] при 3 > А доказали оценку ю < 11. Оре [19] установил, что если 6 = 5, то и** < 12. Из теоремы 1.13 диссертации следует, что при <5 > 4 либо ¡/* £ 11, либо и* < 9. причем обе оценки достижимы.

В § 1.3 рассматриваются различные аспекты задачи об отделимости цикла. Усиливая результаты Лебега [16], Коциг [15] доказал, что в плоской триангуляции с 6 = 5 минимальный вес грани, ш , не превосходит 16 и предположил, что точная оценка здесь 17. С другой стороны, Грюнбаум [11] предположил, что циклическая связность 5-связных плоских графов не превосходит 11, т.е. удалением не более 11 ребер можно получить две компоненты связности, содержащие цикл. Промежуточный результат в этом направлении был получен Пламмером (1972). Решение задач Коцига и Грюнбаума дает

ТЕОРЕМА 1.16. В любом плоском графе с б = 5 есть 3-грань веса не более 17; оценка точна.

Ясно, что граница 3-грани веса не более 17 отделяется от остальной части графа не более чем 11 ребрами. При 5 < 5, как показывает пример двойной п-пирамиды, ид не ограничен. Но оказывается, что при запрещении в триангуляции лишь 4-вершин, становится ограниченным (этот факт не был известен Лебегу

[16]). А именно, Коциг [16] для плоских триангуляции доказал, что если нет 4-вершин, то шд< 39, а если нет ни 4-, ни 5-вер-

шин, то щд < 34, и предположил, что в обоих случаях < 29.

ТЕОРЕМА 1.17. Если в плоской триангуляции нет 4-вершин, то шд < 29. причем двукратное подразделение граней икосаэдра

дает w = 3 + 2(3 + 2 -5) =29.

А

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

ТЕОРЕМА 1.16'. Если в плоском графе б > 3 и нет 3-й 4-граней, то найдется 3-вершина « с в(») s il.

Пламмер и Тофт [21], используя теорему Лебега [16], доказали, в частности, что в многограннике с максимальным рангом грани R существует младшая вершина v с е(и) s R +9 при R > 3 и даже с(и) s й + 3 при R > 42. Заметим, что в R- призме кавдая вершина . v инцидентна Я-г рани и двум 4-граням, откуда з(и)=К-2 + 4- 2 + 4- 2 = Я + 2. .

ТЕОРЕМА 1.16. В эйлеровом многограннике найдется такая . младшая вершина и, что o(v) < 21 при R <16; о( и) < R + 4 при 16 < R < 19; 0(и) < R + 3 при 19 < R < 23 И o(V) < R ■+ 2 при R > 24.причем оценка e(v) < R + 2 достишда при любом R > 3.

В § 1.4 приводятся оценки для числа легких ребер и граней. Пусть е. - число ребер, соединяют i-вершины с J-вершинами; аналогично, f.' . k - число 3-граней, в границу

которых входит {-вершина, ,/-герикна и к-вершина. Давно подучено, что если в том или ином классе плоских графов ы или ьГ ' ограничено сверху числом- U, то элементов с весом не более, и (называем в этом контексте легкими) довольно гиного. Так, Веркике [25]' еще в 1904 г. для многогранников с , <5 = 5 доказал, .что еа а' + е, 6 >0. Гркнбаум [12], после ■

опсоверкения Фиском [12, с. 131] его гипотезы 2е + е гбО. навеякнсй тем, что'из ез 5= 0 следует. ез ег 60 [10], доказал более слабую оценку. 4ед д + ея > 60.

ТЕОРЕМА 1.23. Для .плоских графов с 5 = 5 выполняются неравенства. -

(а) 2- е + е > 60;

7 5,5 5,6

(б) 2е + е + - е 2 60.

5, 5 5, S 7 5,7

причем все коэффициенты, кроме, быть может, первого в (а),

являются наилучшими из возможных.

Грюнбаум Ш] предположил, что теорема Коцига [14] о весе

ребра в многограннике допускает усиление вида

Е а. . е. . г 120 i+jsiз l'-> *■••>

(при конкретных а£ .). Юцович [133 получил для многогранников соотношение такого' типа, но с другими значениями . и поставил вопросы о наилучшем из подобных соотношений для' (а) многогранников; (б) плоских нормальных карт; (в) карт с 6 > 4 и (г) карт без 3- и 5-вершин. Напомним, что карта нормальна, если 5 г з и нет граней ранга меньше 3.

ТЕОРЕМА 1.20. Для плоских нормальных карт имеет место оценка

40е + гъв + 16е + Юе + б^-е + 5е + Z- е +

э,з 3,4 3,5 з, е з з, 7 а, в г а, в

+ 2е + 16- е + lie + 5е + 1- е +

3, Ю 3 4,4 4,5 4, S 3 4,7

+ 5*- е + 2е > 120,

3 5,5 5, в

причем каждый коэффициент является наилучшим из возможных.

К счастью, исчерпывающие ответы на остальные вопросы Юцовича весьма просто извлекаются из теоремы 1.20 (априори на это рассчитывать не приходилось). А именно, для многогранников наилучшая система коэффициентов получается всего лишь заменой аз с 40 на 20, для карт с а г 4 вычеркиванием членов,

содержащих индекс 3, а для карт без 3- и 5-вершин - содержащих индексы 3 или 5.

Для плоских триангуляций с 6 = 5 Вернике [25] доказал,

что е + е >0. Аппель и Хакен [53 - что е + / >0,

3, 3 3, 6 5,5 5,6,6

а Лебег [16] - что / + г / + / + / +

5,3,5 3 5,5,6 5,5,7 5,5,8

+ / + / + / г 20. Теорему 1.16 можно записать как

'5,5,9 5, 6, 6 5,6,7 ~ •>

f к + f +/ +/ >0. Приведенные в диссерта-

ции конструкции показывают, что в последнем неравенстве ни один член не является излишним. В частности, триангуляция с параметрами /555=/5!56=/5ее=0 подчеркивает неулучшаемость теоремы Франклина (1922) о существовании 5-вершины,

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

ТЕОРЕМА 1.24. Если в плоском графе а = 5. то 18/= в 5+ + 9/ + 5/ +4/ > 144, причем каждый коэффициент,

5, 5, 6 3, 5, 7 5, б, б 1

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

Глава 2 посвящена задачам цикловой, совместной и предписанной раскрасок; в ней существенно используются результаты и идеи главы 1. В § 2.1 дается введение в проблематику раскрасок. В § 2.2 решается поставленная в 1965 г. задача Рингеля о 6 красках. Граф 1-планарен, если его можно вложить в плоскость так, чтобы каждое из ребер пересекалось не более чем с одним ребром. Рингель [23] доказал, что 1-планарные графы вершинно 7-раскрашиваемы и предположил, что они 6-раскрашиваемы. Поскольку К 1-планарен, менее чем 6 красками не обойтись.

ТЕОРЕМА 2.1. Если граф 1-планарен, то он 6-раскрашиваем.

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

ТЕОРЕМА 2.1'. Если граф плоский, то х 5 6.

Последняя оценка также неулучшаема ввиду примера 3-призмы, в которой подлежат окраске 11 элементов, но в один цвет может быть окрашено, как нетрудно проверить, не более двух элементов. Ранее оценка * < 6 была доказана Рингелем [23] для триангуляции, а Аркдиконом [6] для противоположного частного случая - плоских графов без треугольников, причем в [6] подчеркивалось,что идея решения не годится в общем случае.

Наконец, вершины плоского графа, в котором грани имеют ранг не более 4, можно раскрасить в 6 цветов так, чтобы вершины в границе каждой из граней были окрашены попарно-различно.

ТЕОРЕМА 2.1". Если граф плоский, то ^ < 6.

Первая и третья формулировки теоремы о 6 красках легко сводятся друг к другу, а вторая следует из них. Диссертанту не известно, существует ли простой вывод теорем 2.1 и 2.1" из теоремы 2.1'.

В § 2.3 изучаются к-цикловые раскраски, введенные Ope и Плашером [201 и предполагающие, что в границах граней ранга не более к цвета вершины не повторяются. Наименьшее число цветов, требуемое для. к-цикловой раскраски графа обозначается хк. В [203 доказано, что xk £ 2к при к г 3. Уточнение этой оценки при к ~ 3 дает теорема о 4 красках С5], а при к = 4 -теорема 2.1".

ТЕОРЕМА 2.2. . Если граф плоский, то xs £9, х. < 10, < 12 и xk < 2k - 3 при к г 8.

Для многогранников, т.е. 3-связных плоских графов, оценка Ope и Пламмера была существенно улучшена Плашзром и Тофтом [21]: xk < к + 9 (в классе всех плоских графов данная оценка неверна). Точнее, они показали, что xk< к + 7 при кг 15, xk < к + 6 при к г 18, xk < к + 5 при к > 24 и наконец, хк < к + 4 при к > 42. В [21] высказывалась гипотеза xk £ < к + 2 при к > 3. Следующая оценка находится на полпути между оценкой Пламмера и Тофта и их гипотезой.

ТЕОРЕМА 2.3. Для любого многогранника имеют место оценки xk £ 21 при к £ 16; xk £ к + 5 при 16 < к £ 19; хк s к + 4 при 19 < к < 23 и xk £ к + 3 при к > 24.

При малых к оценка теоремы 2.2 для произвольных плоских графов лучше, чем в [21] для многогранников. Теорема 2.3 вытекает из оценки для цикловой степени теоремы 1. lô и теоремы 3.1 главы 3 о стягиваемых ребрах многогранников.

Переходим к описанию результатов по совместным и предписанным раскраскам (§ 2.4). Идея совместной раскраски различных элементов графа - вершин,. V, и/или ребер, Е, и/или граней, F,

принадлежит Рингело [23]; по определению, соседние элементы должны краситься в разные цвета. Если в набор окрашиваемых элементов не входят ребра, то согласно теореме 2.1', * 5 6.

В противном случае, т.е. для чисел \д и * , а также

для хроматического индекса х , в верхнюю оценку входит максимальная степень Л, так как при вершине степени Д, ребра окрашиваются попарно-различно.

Гипотеза Визинга [2] - Бехзада (1966) о тотальной раскраске гласит: х < Д + 2 для любого (не только плоского) графа. К. настоящему времени она подтверждена линь при Д < 5 (Косточка, [4]). Задача нахождения х ИР-трудна (Санчез-Аррое, 1990). ""

ТЕОРЕМА 2.4. Если граф плоский, то х < Д + 2 при Д * {6,7,6} и = Д + 1 при Д г 14.

В 1973 г. Кронк и Митчем [17] предположили,что < Д+4 для любого плоского графа и доказали это предположение при Д = 3. Довольно долго продвижений по этой задаче не было [24, проблема 1.10], за исключением того, что теорема 2.1' и теорема Визинга [2]: хд = Д для плоских графов с Д > 6, вместе дают оценку х < Д + 6 при Д > 6. Наконец, в [30] гипотеза

Кронка-Митчема была доказана диссертантом для Д > 12, а затем в [31, 36] ограничение на Д ослаблялось за счет привлечения более мощных структурных леш из § 1.2. Последние из результатов в этом ряду представляет

ТЕОРЕМУ 2.6 и 2.7. Если плоский граф имеет Д > 7, то

хуе/ < Д + 4, а если Д > 12, то х £ Д + 2, причем оценка неулучшаема.

Звезда К А имеет как раз х ЛК ) = Д + 2, так как

1, Л 1 ив} 1, А

центральная вершина, все Д ребер и единственная бесконечная грань суть Д + 2 попарно соседних элемента. Таким образом, гипотеза Кронка-Митчема трансформировалась в задачу отыскания точной оценки для при Д, которая фактически остается неизвестной при Д от 4 до 11.

Для реберно-граневых раскрасок Мельников [22, с.5433 по

аналогии предположил х < Д + 3.

& *

ТЕОРЕМА 2.10. Если плоский граф имеет Д > 10,то * < Д+1, причем оценка неулучшаема.

В отличие от обычной раскраски, в предписанной раскраске [33, независимо введенной также Эрдешем и др. в 1979 г., множество допустимых цветов меняется от одного элемента к другому. Нужно доказать, что если предписание у каждого элемента достаточно велико, то из него можно выбрать цвет так, чтобы на любых соседних элементах были выбраны разные цвета. Заманчивое для многих обобщение х 5 д + 1 известной теоремы Визинга [13 на предписанный случай пока получено лишь при Д < 3.

ТЕОРЕМА 2.11. Если у плоского графа Д > 9, то х < д + 1,

а если Д > 14, то х = Д.

в

Резюмируя изложение глав 1 и 2, составляющих ядро диссертации, обратим внимание, во-первых на тесную связь между цикловой и вершинно-граневой раскрасками с одной стороны и цикловой степенью, циклической связностью и весом грани с другой. Во-вторых, на возможность получать оценки в задачах совместной раскраски с участием ребер и предписанной раскраски ребер, т.е. для чисел хуе, и * , опираясь на теоремы о весе ребра.

В главе 3 находятся результаты либо вспомогательные, либо близкие по тематике. Ребро, стягивание которого оставляет граф 3-связным, называется стягиваемым. Вершина симплициальна, если инцидентна лишь 3-граням.

ТЕОРЕМА 3.1. Если вершина у многогранника симплициальна, а |К| > г{V) + 1, где г(у) - ее степень, то и инцидентна не менее чем 6 - г(г» стягиваемым ребрам.

С точки зрения возможности усиления теоремы 3.1, остается • открытым единственный частный вопрос: всякая ли симплициальная 6-вершина в достаточно большом многограннике инцидентна хотя бы одному стягиваемому ребру?

В § 3.2 рассматривается один из вариантов задачи раскраски 1-вложимых графов [24, проблема 2.73. А именно, установлен

максимум хроматического числа графов, 1-влошмых в псевдоплоскость в смысле Кайнена, т.е. когда в особых точках скрещиваются ребра графа. Согласно теореме 2.1, х+(Р) = 6. ТЕОРЕМА 3.2.

§ 3.3 посвящен изучению сопряженных раскрасок [24, проблема 1.11] вершин триангуляций.при которых не только смежные, но и сопряженные относительно ребра вершины должны быть окрашены в разные цвета.В [9] Буше, Фуке, Жоливе и Ривьер построили плоскую триангуляцию с сопряженным хроматическим числом хс < 9 и доказали, что для плоскости хс < 12.

ТЕОРЕМА 3.3. Каждая плоская триангуляция имеет хс < П.

Для триангуляция регулярной поверхности б" с эйлеровой характеристикой N в [9] получена оценка хс < 6 + у 49 - 24«. Напомним, что и принимает значения от 2 до Следующая теорема дает асимптотически в {2Г лучшую оценку, которая, по-видимому, точна для всех б™, отличных от плоскости.

ТЕОРЕМА 3.4. При N * 2 триангуляция поверхности имеет хс £ К+ V 169 - Ш)/2].

В & 3.4 строятся специальные представления графов на поверхностях. Проблема Хивуда об империях поставлена более 100 лет назад и к настоящему времени решена для 25 ■/. поверхностей (3 класса вычетов по модулю 12) [24, проблема 2.1]. Для поверхностей малого рода (близких к плоскости М = 2) оставался открытым лишь вопрос о возможности представления К в виде 2-империи на бутылке Клейна. Рингель, Джексон и Хартсфилд (1965) полагали,что такого представления не существует. Однако имеет место

ТЕОРЕМА 3.6. К представим в виде 2-империи на бутылке Клейна.

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

при п = 4.

при 0 5 п * 4;

ТЕОРЕМА 3.6. К ' представим в виде объединения тороидального и клейнова графов.

Аналогичное разбиение К на два тороидальных графа построено Рингелем еще в 1956 г., а разбиения К на два клейновых графа до сих пор не найдено. Мейер одновременно и независимо доказал теорему 3.6; оба решения приведены в [53].

В заключительном § 3.5 главы 3 содержится результат, опубликованный в книге, посвященной 60-летию Вагнера,

.ТЕОРЕМА 3.10. Псевдотриангуляции любой ориентируемой поверхности на одном и том же множестве вершин переводимы друг в друга посредством диагонального преобразования.

Для триангуляции (петли и кратные ребра запрещены) плоскости такая теорема была доказана в 1936 г. Вагнером, позднее для тора - Дыодни, а для проективной плоскости - Негами и другими.

В заключение хочется поблагодарить сотрудников отдела теоретической кибернетики ИМ СО РАН, российских и зарубежных коллег за внимание и поддержку.

." ЛИТЕРАТУРА.

1. Визинг В.Т. Об оценке хроматического числа р-графа // Дискретный анализ. - Новосибирск, 1964. - Вып. 3. -С. 25-30.

2..Визинг В.Г. Критические графы с данным хроматическим классом // Дискретный анализ..-. Новосибирск, .1965. - Вып. 5. -.С. 9-17.

3. Визинг В. Г. Раскраска вершин графа в предписанные . цвета // Методы дискретного, анализа в теории кодов и схем.. -Новосибирск, 1976. - ВЫП. 29. - С. 3-10.

4. Косточка A.B. Аналог оценки Шеннона для тотальных раскрасок //Дискретный анализ. - Новосибирск, 1977. - Вып. 30. - С. 12-22.

5. Appel К., НаКеп V. The existence of unavoidable sets of geographically good configurations // Illinois J. Math. - . 1976. - V. 20. - P. 218-297.

6.Archdeacon D. Coupled coloring of planar maps // Congressus Munierantium. - 1983. - V. 39. - P. 89-99.

7. BodendieK R., Schumacher H., Wagner K. Uber das Ringelsche Sechsfarbenproblem // Praxis Hath. - 1983. - V. 25. - P. 353-356.

6. Bodendiek R. Ringelsche Sechsfarbenprobllem ist gelost // Praxis Math. - 1986. - V. 28. - P. 52-53.

9. Bouchet A., Fouquet J.-L., Jolivet J.-L., Riviere M. On a special face colouring of cubic graphs // Ars Combinatoria. - 1987. - V. 24. - P. 67-76.

SO. Grunbaum B. Acyclic colorings of planar graphs // Israel J. Math. - 1973. - V. 14. - P. 390-408.

11. Grunbaum B. New views on some old questions of combinatorial geometry // Proc. Intern. Colloq. Rome, 1973 / Accademia nacionale dei 1 i neei.-Roma, 1976. - P. 451- 468.

12. Grunbaum B.,. Shephard G.C. Analogues for til lings of Kotzig's theorem on minimal weight of edges // Annals of discrete math. - 1981. - V. 12. - P. 129-140.

13. Jucovic E. Strengthening of a theorem about 3- poly topes // Geom.dedicata. - 1974. - V. 13. -P. 20-34.

14. Kotzig A. Contribution to the theory of eulerian polyhedra // Mat. Cas. - 1955. - V. 5. - P. 101-103.

15. Kotzig A. From the theory of Euler's polyhedrons // Mat. Cas. - 1963. - V. 13.' - P. 20-34.

16. Kotzig A. Extremal polyhedral graphs // Proc. Second Intern. Conf.on Combin. Math. /New-YorK, 1978. - P. 569-570.

17. KronK H., Mitchem J. A seven-color theorem on the sphere // Discrete Math. - 1973. - V. 5. - P. 253-260.

16. Lebesgue H. Quelques consequences simple de la formule d'Euler //J. math, pure applic. - 1940. - V. 9. - P.27-43.

19. Ore O. The four color problem // Academic Press / New YorK-London, 1967. - 259 p.

20. Ore 0., Plummer M.D. Cyclic coloration of plane graphs //Recent progr. in comb. / Hew York, 1969. - P. 287-293.

21. Plummer M.D., Toft B. Cyclic coloration of 3-polytopes // J. Graph Theory. - 1987. - V. 11. - P. 507-516.

22. Recent advances in graph theory / Proc. Intern. Symp. Prague, 1974. - Academia, Praha. - 1975. - 544 p.

23. Klngel G. Ein Sectisfarbenproblem auf der Kugel // ■Abh. Math. Sem. Univ. Hamburg. - 1965. - V. 29. - P 107-117.

24. Toft B. Graph colouring problems.I. // Preprint Odense Uníversitet. - 1987.

25. WernicKe P. Uber den Kartographischen Vierfarbensatz // Math. Ann. - 1904. - V. 58. - P. 413-426.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

26. Бородин O.B. Решение задач Рингеля о вершинно-граневой раскраске плоских графов и раскраске 1-планарных графов // Методы дискретного анализа в изучении реализации логических функций.- Новосибирск, 19Ô4. - Вып. 41. - С. 12-26.

27. Бородин О.В. О раскраске 1-вложимых графов // Тез. докл. VII Всесоюн. конф. по проблемам теор. кибернетики, Иркутск, сент. 1965. - Иркутск, 19Ô5. - Ч. 1. - С. 30.

20. Бородин О.В. О цикловой раскраске вершин плоских графов //Тез. докл. I Всемирного конгресса об-ва матем. статистики и теории вероятностей им. Бернулли. - М. : Наука, 19Ô6. -1.2. - С. 499.

29. Бородин О.В. О хроматическом числе графов, 1-влошмых в. псевдоплоскость // Методы дискретного анализа в теории графов и логических функций.- Новосибирск, 1986. - Вып. 43. -С. 3-11.

30. Бородин О.В. Совместные раскраски графов на плоскости // Методы дискретного анализа в решении комбинаторных задач. -Новосибирск, 19Ö7. - Вып. 45. - С. 21-27.

31. Бородин О.В. Совместная раскраска вершин, ребер и граней плоских графов // Методы дискретного анализа в исследовании функциональных систем. - Новосибирск, 19ôô. -ВЫП. 47. - С. 27-37.

32. Бородин О.В. Верхняя оценка ддя сопряженной раскраски вершин плоских триангуляции // Гез. докл. VIII Всесоюзн. конф. по проблемам теор. кибернетики, Горький, I960. - Ч. 1. -

С. 53-54.

33. Бородин О.В. Решение, задач Коцига и Грюнбаума об отделимости цикла в плоских графах // Математические заметки.

- 1969. - Т. 46, №5. - С. 9-12.

34. Бородин О.В. Оценки для числа легких ребер в плоских графах // Препринт ИМ СО АН СССР. - Новосибирск, 1969. - № _ 6.

- 12 с.

35. Бородин О.В. Обобщение теоремы Коцига и предписанная раскраска ребер плоских графов // Математические заметки. -

1990. - Т. 46, tt-6. - С. 22-26.

36. Бородин О.В. Совместное обобщение теорем Лебега и Коцига о комбинаторике плоских карт// Дискретная математика. -

1991. - Т. 3, №4. - С. 24-27.

37. Бородин О.В. Минимальный вес грани в плоских триан-гуляциях без 4-вершин // Математические заметки. - 1992. -Т. 51, № 1. - С. 16-19.

36. Бородин О.В. Структурная теорема о плоских графах и ее приложение к раскраске // Дискретная математика. - 1992. -Г. 46, № 1. - С. 60-65.

39. Бородин О.В. Строение окрестности ребра в плоском графе и совместная раскраска вершин, ребер и граней //Матем. заметки. - 1993. - L53, № 5. - С.35-47.

40. Бородин О.В. Совместные раскраски и раскраски 1-вложимых графов //30 Intern. Wiss. Koll. ТН Ilmenau. - 1985.

- P. 19-20. .

41. Borodin 0.V. New structural properties uf planar graphs with application in coloring // 33 Intern. Wiss. Koll. TH Ilmenau. - 1986. - P. 159-162.

42. Borodin О.V. Representing of. К as a 2-pire шар on the Klein bottle // J. reine angew. Math. - 1989. - V. 393. -P. 132-133.

43. Borodin 0.V. On the total coloring of planar graphs // ibid. - V. 394.' - P. 180-185.

44. Borodin 0.V. Computing light edges in planar graphs / Topics in Combinatorics and Graph Theory.- Eds.: R.BodendieK and R.Henn. - Physica-Verlag Heidelberg, 1990. - P. 137-144.

45. Borodin O.V. A structural property of planar graphs and the simultaneous coloring of their edges and faces // Mathematica Slovaca. - 1990. - V. 40. - P. 113-116.

46. Borodin 0.V. Diagonal ll-colorlng of plane triangulations // J.Graph Theory. - 1990. - V.14. - P.701-704.

47. Borodin 0.V. Minor faces of plane graphs 'with the minimal degree 5 / Proc. of Intern, conf. "Discrete Math.", Eisenach, Germany. - 1990. - P. 12-15.

48. Borodin O.V. Diagonal transforming triangulations of orientable surfaces / Contemporary Methods in Graph Theory.-Ed. R.Bodendiek.- BI Vissenschaftsferlag, Mannheim /Wien/Zurich. - 1990. - P. 169-180.

49. Borodin O.V. Precise lower bounds for the number of light edges in planar graphs / Abstracts of Fourth Czecho-Slovak Intern. Symposium on Combinatorics, Prachatice.

- 1990. - P. 41.

50. Borodin O.V. Structural properties of planar maps with the minimum degree 5 // Mathematische Nachrichten.- 1992.

- V. 158. - P. 109-117.

51. Borodin O.V. Diagonal coloring the vertices of triangulations // Discrete Math. - 1992. - V. 102. - P. 95-97.

52. Borodin O.V. Joint extension of two Kotzig's theorems on 3-polytopes // Combinatorica. -1992. - V. 13, № 1,- P. 121-125.

53. BorodinO.v., Mayer J. Decomposition of K13 into a torus graph and a graph inbedded in the Klein bottle.-Discrete Math. - 1992. - V. 102. - P. 97-98.

54. Borodin O.V. Structural properties and colorings of plane graphs 1 Combinatorics, Graph Theory, Complexity - Eds.: M.Fiedler and J.Nesetril.- Proc. of Fourth Czecho-SlovaK Intern. Symposium on Combinatorics, Prachatice. - 1990. -P. 31-37.

55. Borodin O.V. Precise lower bounds for the number of edges of minor weight in planar maps // Mathematica Slovaca. -1992. - V. 42, №. 2. - P. 129-142.

56. Borodin O.V. Cyclic coloring of plane graphs // Discrete Math. - 1992. - V. 100. - P. 281-289.

57. Borodin 0.V. An extension of Kotzig's theorem on the minimum weight of edges in 3-polytopes // Mathemartica Slovaca. - 1992. - V. 42, №. 4. - P. 385-389.

58. Borodin O.V. Four problems on plane graphs raised by BranKo Grunbaum / Graph Structure theory. - Eds. N.Robertson and P.Seymour. - Proc. of Graph Minors Conference, Seattle, 1991. //Contemporary Math. - 1993. - V. 147. - P. 149-156.

59. Borodin O.V. Simultaneons coloring of edqes and faces of plane graphs //Discrete Math. - 1994. - V. 128. - P.21-33,