Ориентированная и 2-дистанционная раскраски плоских графов с заданным обхватом тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

российская академия наук

и СИБИРСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

ООЗОВТ1ЭЕ

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

Иванова Анна Олеговна

ОРИЕНТИРОВАННАЯ И 2-ДИСТАНЦИОННАЯ РАСКРАСКИ ПЛОСКИХ ГРАФОВ С ЗАДАННЫМ ОБХВАТОМ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Новосибирск, 2006

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

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук О. В. Бородин доктор физико-математических наук А. Д. Коршунов, кандидат физико-математических наук В. А. Аксенов Институт систем информатики СО РАН

Защита состоится " 17 " января 2007 г. в 16 часов на заседании диссертационного совета Д 003.015.01 в Институте математики им. C.JI. Соболева СО РАН по адресу: пр. Коптюга 4, 630090, г. Новосибирск.

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

Автореферат разослан " " декабря 2006 г.

Ученый секретарь диссертационного совета, д. ф.-м. н. V Ю. В. Шамардин

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

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

Раскраска плоских графов также представляет собой широкую область исследования, выросшую из знаменитой проблемы четырех красок, решенной в 1976 г. К. Аппелем и В. Хакеном [2, 3, 4], в настоящее время в ней работают сотни специалистов. Доказательство теоремы о четырех красках основано на построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другой пример того же рода — это построенная О.В. Бородиным [1, 7] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную раскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, — ациклический). Теорема О.В. Бородина об ациклической 5-раскраске включена во введении книги В.Тофта и Т. Йенсена [15] в число 40 важнейших результатов по раскраске графов за все годы. В последнее время в работах зарубежных математиков эта теорема получила ряд приложений к другим задачам раскраски. В главе "Плоские графы" этой книги цитируются более 20 результатов О.В.Бородина, A.B.Косточки, В.А.Аксенова и Л.С.Мельникова.

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

обхвата д(О), т. е. длины минимального цикла. Нетрудно показать, что если граф С? плоский, то тас?((7) < • ^ ДРУГ0Й стороны, в силу известной теоремы Эрдеша (1959) о раскраске случайных графов, существует (неплоский) граф (?, имеющий произвольно большие д(О) и гпас1(0). Часть результатов диссертации доказывается для произвольных разреженных графов, т. е. с использованием максимальной средней степени, а не обхвата.

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

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

За пределами теории графов интерес к 2-дистанционной раскраске объясняется тем, что и она сама и такие ее обобщения как (р, д)-раскраска и предписанная (р, <?)-раскраска являются одной из естественных моделей в проблеме распределения радиоча-

стот в сетях мобильного телефонирования. А именно, при (р, q)-раскраске плоского графа его вершины (передатчики) должны быть раскрашены (получить частоты) так, чтобы цвета вершин (целые числа) на расстоянии 1 различались не менее, чем на р, а на расстоянии 2 — не менее, чем на q. Здесь р ^ д, так как частоты ближе расположенных источников должны различаться сильнее ввиду интерференции волн. В частности, (1,1)-раскраска есть 2-дистанционная раскраска. При этом иногда каждый источник имеет свой собственный набор разрешенных' частот, т. е. возникает известная в теории графов задача предписанной раскраски.

Цель работы состоит в получении новых результатов о рас- • красках (ориентированных и 2-дистанционных) разреженных графов, в основном плоских, а также вспомогательных результатов о строении таких графов.

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

Научная новизна. В диссертации получены следующие основные результаты.

1. Установлено структурное свойство минимальных графов, не допускающих гомоморфизмов на С(5; 1,2) и цикл Съ (отсутствие так называемых "мягких" циклов), из которого, в частности вытекает, что любой плоский граф обхвата не менее 12 имеет ориентированную 5-раскраску.

2. Доказана ориентированная 7-раскрашиваемость плоских графов обхвата не менее 7.

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

4. Получены достаточные условия (в терминах максимальной степепи Д(С) и обхвата <?((?)), при которых 2-дистанционное хроматическое число Х2(&) графа (? достигает своей нижней

границы Д(С7)4-1. В частности, это имеет место при: (а) Д(С)=3 и ^ 24; (б) д(0 > 8 и А (С) ^ 15.

5. Ввиду того, что существует плоский граф С? с #((?) ^ 6, для которого (С?) > Д(С0 +1 при произвольно большом А(С), при д((?) = 6 для выполнения равенства = Д(С?) +1 были

найдены дополнительные ограничения на структуру графа. А именно, это равенство имеет место, если Д((7) ^ 179, а каждое ребро инцидентно 2-вершине (последнее условие выполняется, в частности, для тотальных графов).

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

Апробация работы. Все изложенные в диссертации доказательства подробно разбирались на семинаре "Теория графов" Института математики СО РАН в 2004-2006 гг.. Доклад с обзором результатов диссертации был сделан на научной конференции X Лаврентьевских чтений, посвященных 50-летию Якутского госуниверситета (2006), и получил I премию на секции "Математика, механика и физика". Работа автора по раскраске плоских графов в 2005-2006 гг. поддержана грантами РФФИ 0601-00694 и 05-01-00816, а в 2006 — грантом ректора Якутского государственного университета имени М.К. Аммосова.

Публикации. По теме диссертации опубликованы 5 статей в журнале "Сибирские электронные математические известия" [17]-[20], [26], 2 статьи в журнале "Дискретный анализ и исследование операций" [21, 22], 2 статьи в журнале "Математические заметки ЯГУ" [24, 25] и статья в сборнике трудов X Лаврентьевских чтений [23].

Структура и объем диссертации. Объем диссертации составляет 79 страниц. Она состоит из введения, двух глав и списка литературы, содержащего 58 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе содержатся результаты об ориентированных и круговых раскрасках разреженных графов (не обязательно плоских).

Ориентированная ^-раскраска орграфа С? есть гомоморфизм из С в некоторый ¿-вершинный турнир Н (мишень), т. е. отображение (р из У(£?) в У(Н), при котором ху е Е{р) =Ф- <р(х)(р(у) 6 Е(Н). Другими словами, вершины орграфа Я считаются цветами и каждой вершине из С требуется приписать цвет так, чтобы любая дуга в О, начало которой окрашено в цвет г, а конец — в имелась бы в мишени Н.

Ориентированное хроматическое число о{0) определяется как минимальное к, при котором О имеет ориентированную /г-раскраску. Ориентированное хроматическое число графа может существенно превосходить его хроматическое число. Например, существуют двудольные графы с произвольно большим ориентированным хроматическим числом (достаточно заменить каждое ребро графа Кп на путь длины 2, и тогда концы каждого такого пути в полученном графе К*, т. е. все вершины исходного графа Кп, обязаны краситься в разные цвета, так как в мишени нет антипараллельных дуг).

Ориентированное хроматическое число было введено Кур-селем [11] при изучении логик второго порядка на графах. В частности, он доказал, что о{в) < З63 для любого плоского графа (5, а в [14] данная оценка была улучшена до 80 (с использованием ациклической 5-раскрашиваемости плоских графов, доказанной О-В. Бородиным в [7]). Для разреженных плоских графов к 2005 г. были известны следующие результаты (Бородин, Вест, Ким, Косточка, Нешетрил, О лам, Распо, Сопена, см. [9, 10, 12, 13, 14]):

Пусть (7 - плоский граф обхвата д(0). Тогда:

(1) о(С) ^ 59 при $(<3) ^ 4;

(и) о{в) ^ 19 при д{С) > 5;

(Hi) o(G) < И при g(G) ^ 6;

(iv) o(G) < 7 при g(G) > 8;

(v) o(G) < 5 при g(G) > 13 и

(vi) существует плоский граф Go с o(Gо) > 4 и произвольно большим обхватом.

Наибольшее значение среди результатов главы 1 имеет

Теорема 1.1. Если орграф G плоский и g(G)^ 12, too(G)^5.

Эта задача была поставлена О.В. Бородиным и A.B. Косточкой около 10 лет назад. При доказательстве данной теоремы решающую роль сыграла идея глобального перераспределения эйлеровых вкладов, не встречавшаяся до сих пор в работах по плоским графам. (Хотя она теоретически ничему не противоречит, реализовать ее ранее не удавалось.) Ключевой в доказательстве является лемма о "мягком цикле", налагающая строгие ограничения на структуру минимального контрпримера. Эта лемма справедлива для графов произвольного обхвата, поэтому будет полезна в дальнейших исследованиях по ориентированным и круговым 5-раскраскам, связанным с гипотезами Татта и Жеже об алгебраических 5-потоках.

Отметим, что в нашей работе [22] эта теорема доказывается в более общем виде: любая ориентация графа (не обязательно плоского) с обхватом не менее 5 и mad[G) < Щ имеет ориентированную 5-раскраску. Как следствие, любая ориентация плоского или проективно плоского графа с обхватом не менее 12 имеет ориентированную 5-раскраску.

Здесь же укажем на связь между задачами ориентированной и круговой раскрасок (библиографию по круговым раскраскам см. в [10]). Для простоты приведем определение круговой раскраски неориентированного графа G в 5 цветов: требуется раскрасить его вершины цветами 0,1,..., 4 так, чтобы цвета любых двух смежных вершин отличались на 2 или 3 по mod 5, что эквивалентно существованию гомоморфизма графа G на цикл С5. Вопрос о круговой 5-раскрашиваемости плоских графов обхвата 12 также оставался открытым в течение нескольких лет. Нам удалось сначала доказать этот факт, а затем уже теорему 1.1. Оба доказательства имеют одинаковую структуру, но в

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

Ориентированная раскраска тесно связана с так называемыми антисимметрическими потоками, а круговая - с гипотезой Жеже (1981) о круговых векторнозначных потоках. В свою очередь, гипотеза Жеже является усилением гипотезы Татта о 5-потоках. Ослабленный вариант гипотезы Жеже состоит в том, что каждый плоский граф обхвата не менее 8 имеет круговую 5-раскраску (при обхвате 7 известны примеры графов, не допускающих круговой 5-раскраски). Таким образом, дальнейшие усилия исследователей будут направлены на доказательство ориентированной и круговой 5-раскрашиваемости плоских графов с обхватом от 11 до 8.

Другим усилением ранее известных результатов является

Теорема 1.2. Если орграф G плоский и g(G)~^7, то o(G)^7.

Отметим, что для плоских графов без треугольников, т. е. с обхватом не менее 4, максимальная средняя степень вершин в таких графах может быть сколь угодно близка к 4, как и в упоминавшихся выше графах К*, но при этом о(К*) растет неограниченно с ростом п. Последний из основных результатов главы 1 состоит в улучшении верхней оценки 59 для ориентированного хроматического числа таких графов до 47.

Теорема 1.3. Если орграф G плоский и g{G)^A, то o(G)^47.

Фактически мы доказываем, что каждый ориентированный плоский граф с обхватом не менее 4 имеет гомоморфизм в турнир Пэли Р(47), т. е. турнир на вершинах 0,1,..., 46, в котором пара ij является дугой из г в j, если и только если j — i + q^ (mod 47), где qk — один из 23 квадратичных вычетов по mod 47. Доказательство использует ряд новых свойств турнира Р(47), найденных нами с помощью компьютера и неожиданно вызвавших интерес у специалистов по алгебраической комбинаторике. Кроме того, при доказательстве теоремы 1.3 было установлено

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

Во второй главе получены достаточные условия (в терминах максимальной степепи А ((7) и обхвата д(0)), при которых 2-дистанционное хроматическое число Х2 {О) графа (7 достигает своей нижней границы А (С) + 1.

Раскраска / : —> {1,2, графа С = (У,Е) назы-

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

В теории графов известна гипотеза Г. Вегнера [16] о том, что Хг(<3) ^ + 1 Для любого плоского графа <3 (см. также

монографию Т.Р. Йенсена и Б.Тофта [15, стр. 51]).

Я. ван ден Хойвел и Ш. Мак Гиннесс [6] доказали, что 2А(С) + 25 для любого плоского графа О, а Г. Агнарсоном и М. Холдорсоном [5] было установлено, что Хг(<3) ^ [|Д((3)]+2 при А(С) ^ 749. Наилучшей из опубликованных верхних оценок для произвольных плоских графов является Х2{О) ^ ["§Д(С7)]+1 при Д(<3) > 47 ([8]).

Очевидно, что ^ ¿М^) +1 Для любого графа С (ввиду

того, что в любом графе есть звезда д(<з))- Возникает вопрос: для каких графов 2-дистанционное хроматическое число равно этой тривиальной нижней оценке? К таким графам относятся, например, все деревья.

Легко видеть, что Х2{С^к+\) = 4, т. е. существуют графы с А(£7) = 2 и произвольно большим обхватом. В [17, 18, 21] нами показано, что если обхват плоского графа С при Д(£?) ^ 3 достаточно велик, то Х2(С) = Д + 1.

В диссертацию включены доказательства только тех резуль-

татов из работ [17, 18], которые принадлежат диссертанту:

Теорема 2.1. Пусть С? — плоский граф, тогда Хг(С0 = Д((?) + 1 в каждом из следующих случаев: (г) Д(б) = 3 и,д{О) ^24; (й) Д(С) ^ 15 и 5(С) ^ 8.

С другой стороны, как показано в [18], существуют графы с 9{@) ^ 6, для которых Х2(@) > + 1 при произвольно

большом А (О). В [18] полностью решен вопрос о том для сколь малых (?((?) можно гарантировать равенство Х2((3) = ДС^) + 1 лишь путем наложения ограничения на Д((?).

При д ((7) = 6, ввиду сказанного выше, для выполнения равенства Х2(С<0 = Д(С) + 1 требуются дополнительные ограничения на структуру графа. Вторым основным результатом второй главы является

Теорема 2.2. Если С — плоский граф обхвата 6, в котором Д(С) ^ 179, а каждое ребро инцидентно 2-вершине, то —

Д(<7) + 1.

В связи с теоремой 2.2 отметим, что известная задача тотальной раскраски графа С (т. е. совместной раскраски его вершин и ребер, при которой любые два смежных или инцидентных элемента получают разные цвета) сводится к задаче 2-дистанционной раскраски вспомогательного графа О*, в котором каждое ребро инцидентно 2-вершине; а именно, получаемого из (3 заменой каждого ребра на цепь длины 2.

В заключение автор выражает искреннюю благодарность своему научному руководителю О.В. Бородину за постановку задач и помощь, оказанную при подготовке диссертации, и А.Н. Глебову за внимательное прочтение рукописей большинства статей и сделанные замечания.

Литература

[1] Бородин О.В. Доказательство гипотезы Б. Грюнбаума об ациклической 5-раскрашиваемости плоских графов // Доклады АН СССР. 1976. Т. 231, №1. С. 18-20.

[2] Appel К., Haken W. The existence of unavoidable sets of geographically good configurations //.Illinois J. Math. 1976. V. 20. P. 218-297.

[3] Appel K., Haken W. The solution of the four-color-map problem // Scientific American. 1977. V. 237, №4. P. 108-121.

[4] Appel K., Haken W. The four color proof suffices // Math. Intelligencer. 1986. V. 8, №1. P. 10-20.

[5] Agnarsson G., Hallddrsson M. M. Coloring powers of planar graphs // Unpublished manuscript, 2000.

[6]. Van den Heuvel J., McGuinness S. Colouring the square of a planar graph // Unpublished manuscript, 1999.

[7] Borodin O.V. On acyclic colorings of planar graphs // Discrete Mathematics. 1979. V. 25. P. 211-236.

[8] Бородин О.В., Брусма X., Глебов А.Н., Ван ден Хойвел Я. Минимальные степени и хроматические числа квадратов плоских графов // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8, №4. С. 9-33.

[9] Borodin О.V., Kostochka A.V., Nesetril J., Raspaud A. and Sopena E. On the maximum average degree and the oriented chromatic number of a graph // Discrete Mathematics. 1999. V. 206. P. 77-90.

[10] Borodin O.V., Kim S.-J., Kostochka A.V., and West D.B. Homomorphisms from sparse graphs with large girth // Journal of Combinatorial Theory. Series B. 2004. V. 90. P. 147-159.

[11] Courselle B. The monadic second order logic of graphs VI: On several representations of graphs by relational structures // Discrete Appl. Math. 1994. V. 54. P. 117-149.

[12] Nesetril J., Raspaud A. and Sopena E. Colorings and girth of oriented planar graphs // Discrete Math. 1997. V. 165-166, № 1-3. P. 519-530.

[13] Ochem P. Oriented colorings of triangle-free planar graphs // Inf. Process. Lett. 2004. V. 92, №2. P. 71-76.

[14] Raspaud A. and Sopena E. Good and semi-strong colorings of oriented planar graphs // Inf. Processing Letters. 1994. V. 51. P. 171-174.

[15] Jensen T. R., Toft B. Graph coloring problems // New York. John-Wiley & Sons. 1995.

[16]- Wegner G. Graphs with given diameter and a coloring problem // Technical Report. University of Dortmund. 1977.

Публикации автора по теме диссертации

[17] Бородин О.В., Иванова А.О., Неустроева Т.К. 2-дистанци-онная раскраска разреженных плоских графов // Сибирские Электронные Математические Известия. 2004. Т. 1. С. 76-90.

[18] Бородин О.В., Глебов А.Н., Иванова А.О., Неустроева Т.К., Ташкинов В.А. Достаточные условия 2-дистанционной (А-Ы)-раскрашиваемости плоских графов // Сибирские Электронные Математические Известия. 2004. Т. 1. С. 129141.

[19] Бородин О.В., Иванова А.О. Ориентированная 7-раскраска плоских графов с обхватом не менее 7 // Сибирские Электронные Математические Известия. 2005. Т. 2. С. 222-229.

[20] Бородин О.В., Иванова А.О. Ориентированная раскраска плоских графов с обхватом не менее 4 // Сибирские Электронные Математические Известия. 2005. Т. 2. С. 239-249.

[21] Бородин О.В., Иванова А.О., Неустроева Т.К. Достаточные условия 2-дистанционной (А + 1)-раскрашиваемости плоских графов с обхватом 6 // Дискретный анализ и исследование операций. 2005. Сер. 1. Т. 12, №3. С. 32-47.

[22] Бородин О.В., Иванова А.О., Косточка A.B. Ориентированная 5-раскраска вершин в разреженных графах // Дискретный анализ и исследование операций. 2006. Сер. 1. Т. 1, № 1. С. 16-32.

[23] Бородин О.В., Иванова А.О., Неустроева Т.К. 2-дистан-ционная и ориентированная раскраски разреженных плоских графов // X Лаврентьевские чтения, посвященные 50-летию Якутского государственного университета им. М.К. Аммосова: Научная конференция. Сборник статей. Том I: Секция "Математика, механика и физика" - Якутск: Изд-во ЯГУ. 2006. С. 27-37.

[24] Бородин О.В., Иванова А.О., Неустроева Т.К. О строении младших граней в выпуклых многогранниках // Мат. заметки ЯГУ. 2006. Т. 13. №1. С. 29-44.

[25] Бородин О.В., Иванова А.О., Неустроева Т.К. (р, ¿¡^-раскраска разреженных плоских графов // Мат. Заметки ЯГУ. 2006. Т. 13. №2. С. 3-9.

[26] Бородин О.В., Иванова А.О., Неустроева Т.К. Предписанная (р,д)-раскраска разреженных плоских графов // Сибирские Электронные Математические Известия. 2006. Т. 3. С. 355-361.

Иванова Анна Олеговна

Ориентированная и 2-дистанционная раскраски плоских графов с заданным обхватом

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

Подписано в печать 29.11.06. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ N 147.

Отпечатано в ООО "Омега Принт", пр. Лаврентьева, 6, 630090 Новосибирск.

Введение.

1. Общая характеристика работы

2. Основные понятия и обозначения

3. Обзор результатов диссертации

1. Ориентированные раскраски.

1.1. Обзор и обсуждение результатов главы

1.2. Связь с круговыми раскрасками и алгебраическими потоками

1.3. Доказательство теоремы 1.

1.3.1. Свойства гомоморфизмов в С(5; 1,2).

1.3.2. Основные структурные свойства минимального контрпримера

1.3.3. Завершение доказательства теоремы.

1.4. Доказательство теоремы 1.2.

1.4.1. Структурные свойства минимального контрпримера

1.4.2. Завершение доказательства теоремы

1.5. Доказательство теоремы 1.

1.5.1. Свойства гомоморфизмов в Р(47)

1.5.2. Структурные свойства минимального контрпримера

1.5.3. Завершение доказательства теоремы

2. 2-дистанционная раскраска.

2.1. Обзор и обсуждение результатов главы

2.2. Доказательство теоремы 2.

2.2.1. Случай А (С) =

2.2.2. Случай д ^

2.3. Доказательство теоремы 2.2.

2.3.1. Структурные свойства минимального контрпримера

2.3.2. Завершение доказательства теоремы

1. Общая характеристика работы

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

Раскраска плоских графов также представляет собой широкую область исследования, выросшую из знаменитой проблемы четырех красок, решенной в 197G г. К. Аппелем и В. Хакеном [2, 3, 4], и в которой в настоящее время работают сотни специалистов.

Доказательство теоремы о четырех красках основано на построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другой пример того же рода — это построенная О.В. Бородиным [46, 5] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную ракскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, — ациклический). Теорема О.В.Бородина об ациклической 5-раскраске включена во введении книги В.Тофта и Т. Йенсена [22] в число 40 важнейших результатов по раскраске графов за все годы. В последнее время в работах зарубежных математиков эта теорема получила ряд приложений к другим задачам раскраски. В главе "Плоские графы"этой книги цитируются более 20 результатов О.В. Бородина, A.B. Косточки, В.А.Аксенова и Л.С.Мельникова. Коллектив лаборатории теории графов Института математики СО РАН является одним из мировых лидеров именно в области раскраски плоских графов.

В диссертации изучаются ориентированная и 2-дистанционная раскраски разреженных плоских графов. В теории графов мерой разреженности графа G принято считать максимальную среднюю степень вершин, mad(G), всех его подграфов. Для плоских же графов разреженность обычно выражают в терминах обхвата g(G), т. е. длины минимального цикла. Нетрудно показать, что если граф G плоский, то mad(G) < • С ДРУГ0Й стороны, в силу известной теоремы Эрдеша [14] о раскраске случайных графов, существует (неплоский) граф G, имеющий произвольно большие д(й) и тай{С). Часть результатов диссертации доказывается для произвольных разреженных графов, т. е. с использованием максимальной средней степени, а не обхвата.

Рассматриваемые в диссертации виды раскрасок занимают в теории графов заметное место. Первый из них исследуется с конца 70-х годов, а второй — с начала 90-х. Оба вида раскрасок привлекают интерес специалистов по теории графов как своей математической красотой, так и связями с другими видами раскрасок (ациклической, круговой, тотальной, реберной, (р, </)-раскраской и предписанной) и алгебраической теорией потоков.

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

За пределами теории графов интерес к 2-дистанционной раскраске объясняется тем, что и она сама и такие ее обобщения как (р, д)-раскраска и предписанная (р, д)-раскраска являются одной из естественных моделей в проблеме распределения радиочастот в сетях мобильного телефонирования. А именно, при (р, <?)-раскраске плоского графа его вершины (передатчики) должны быть раскрашены (получить частоты) так, чтобы цвета вершин (целые числа) на расстоянии 1 различались не менее, чем на р, а на расстоянии 2 — не менее, чем на ф Здесь р ^ т. к. частоты ближе расположенных источников должны различаться сильнее ввиду интерференции волн. Понятно, что (1,1)-раскраска есть в точности 2-дистанционная раскраска. При этом иногда каждый источник имеет свой собственный набор разрешенных частот, т. е. возникает известная в теории графов задача предписанной раскраски.

Цель диссертационной работы состоит в получении новых результатов о раскрасках (ориентированных и 2-дистанционных) разреженных графов, в основном плоских, а также вспомогательных результатов о строении таких графов.

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

В диссертации получены следующие основные результаты:

1. Установлено структурное свойство минимальных графов, не допускающих гомоморфизмов на С(5; 1,2) и цикл С5 (отсутствие так называемых "мягких" циклов), из которого, в частности вытекает, что любой плоский граф обхвата не менее 12 имеет ориентированную 5-раскраску.

2. Доказана ориентированная 7-раскрашиваемость плоских графов обхвата не менее 7.

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

4. Получены достаточные условия (в терминах максимальной степепи Д(С) и обхвата #((?)), при которых 2-дистанционное хроматическое число графа (7 достигает своей нижней границы Д((?) + 1. В частности, это имеет место при: (а) Д((?) = 3 и р(0 £ 24; (б) ^ 8 и Д(б?) £ 15.

5. Ввиду того, что существуют плоские графы с <?((?) ^ б, для которых ^(С) > Д((7) + 1 при произвольно большом Д(С?), при д = 6 для выполнения равенства

С) = Д(С?) +1 были найдены дополнительные ограничения на структуру графа. А именно, это равенство имеет место, если Д ^ 179, а каждое ребро инцидентно 2-вершине (последнее условие выполняется, в частности, для тотальных графов).

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

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

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

Всего по теме диссертации автором опубликовано 9 журнальных статей [56, 49, 51,50, 55, 57, 52, 53, 54] и одна статья [58] в трудах конференции. Все вышеперечисленные основные результаты диссертации опубликованы. Некоторые из полученных диссертантом результатов не были включены в диссертацию.

Диссертация состоит из введения, двух глав и списка литературы, содержащего 58 наименований.

1. Agnarsson G., Halldorsson M. M. Coloring powers of planar graphs // Unpublished manuscript. 2000.

2. Appel K., Haken W. The existence of unavoidable sets of geographically good configurations // Illinois J. Math. 1976. V. 20. P. 218-297.

3. Appel K., Haken W. The solution of the four-color-map problem // Scientific American. 1977. V. 237, №4. P. 108-121.

4. Appel K., Haken W. The four color proof suffices // Math. Intelligencer. 1986. V. 8, Л* 1. P. 10-20.

5. Borodin О. V. On acyclic colorings of planar graphs // Discrete Math. 1979. V. 25, №P. 211-236.

6. Borodin O.V., Fon-Der-Flaass D.G., Kostochka A.V., Raspaud A., and Sopena Б. On deeply critical oriented graphs // Journal of Combinatorial Theory. Ser. B. 2001. B81. P. 150-155.

7. Borodin O.V., Kim S.-J., Kostochka A.V., and West D.B. Homomorphisms from sparse graphs with large girth // Journal of Combinatorial Theory. Ser. B. 2004. V. 90. P. 147-159.

8. Borodin O.V., Kostochka A.V., Ne§et?il J., Raspaud A. and SopenaE. On universal graphs for planar oriented graphs of a given girth // Discrete Mathematics. 1998. V. 188. P. 73-85.

9. Borodin O.V., Kostochka A.V., Ne§et?il J., Raspaud A. and Sopena E. On the maximum average degree and the oriented chromatic number of a graph // Preprint 96-336, KAM Series, Charles University, Prague, (1996).

10. Borodin O.V., Kostochka A.V., NeSetril J., Raspaud A. and Sopena E.On the maximum average degree and the oriented chromatic number of a graph // Discrete Mathematics. 1999. V. 206. P. 77-90.

11. Courselle B. The monadic second order logic of graphs VI: On several representaitions of graphs by relational structures // Discrete Appl. Math. 1994. V.54. P. 117-149.

12. DeVos M. Communication at Workshop on Flows and Cycles // Simon Fraser University, June 2000.

13. DeVos M., Ne§etril J. and Raspoud A. Antisymmetric Flows and Edge-connectivity // J. Graph Theory. 1997. V. 24. P. 331-340.

14. Erdos P. Graph theory and probability. Canad. J. Math. 1959. V. 11. P. 34-38.

15. Grotzsch H. Ein Dreifarbersatz fur dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Natur. Reihe. 1959. V. 8, № 1. P.109-120.

16. Griinbaum B. Acyclic colorings of planar graphs // Israel J. Math. 1973. V. 14, №3. P. 390-408.

17. Hell P. and Ne§etr il J. On the complexity of if-coloring //J. Combin. Theory. Ser. B. 1990. V. 48. P. 92-110

18. Haggkvist R. and Hell P. On yl-mote universal graphs // European J. of Combinatorics. Ser. B. 1993. V. 13. P. 23-27.

19. Hell P. and Negetril J. and Zhu X. Duality of graph homomorphisms // Combinatorics, Paul Erdos is Eighty, Bolyai Society Mathematical Studies. 1996. V. 2. P. 271-282.

20. Hell P. and NeSetril J. and Zhu X. Duality and polynomial testing of tree homomorphisms // Transactions of the AMS. 1996. V. 348, №4. P. 1281-1297.

21. Jaeger F. On circular flows in graphs // Finite and Infinite Sets (Eger, 1981), Coloquia Mathematica Societatis Janos Bolyai, North-Holland, Amsterdam. 1984. V. 37 P. 391-402.

22. Jensen T. R., Toft B. Graph coloring problems. New York: John Wiley k Sons, Jnc., 1995.

23. Kotzig A. Contribution to the theory of Eulerian polyhedra // Mat. Casopis. 1955. V. 5. P. 101-113.

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

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

26. Kostochka A.V., Luczak T., Simonyi G. and Sopena E. On the minimum number of edges giving maximum oriented chromatic number // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1999. V. 49. P. 179182.

27. Kostochka A.V., Sopena E. and Zhu X. Acyclic and oriented chromatic numbers of graphs // J. Graph Theory. 1997. V. 24. P. 331-340.

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

29. Marshall T.H. Antisymmetric flows on planar graphs //J. Graph Theory. 2006. V. 52, №9. P. 200-210.

30. NeSetril J. and Zhu X. On bounded treewidth duality of graph homomorphisms // J. Graph Theory. 1996. V. 23, №2. P. 151-162.

31. NeSetril J., Raspaud A. and Sopena E. Colorings and girth of oriented planar graphs // Discrete Math. 1997. V. 165-166, №(1-3). P. 519-530.

32. Ochem P. Oriented colorings of triangle-free planar graphs. Inf. Process. Lett. 2004. V. 92, №2. P. 71-76.

33. Raspaud A. and Sopena E. Good and semi-strong colorings of oriented planar graphs // Inf. Process. Lett. 1994. V. 51. P. 171-174.

34. Samal R. Antisimmetric flows and strong oriented coloring of planar graphs // KAM-Dimata series. 2001. № 510.

35. Seymour P.D. Nowhere-zero 6-flows // J. Combin. Theory. Ser. B. 1981. V. 30. P. 130-135.

36. Sopena E. The chromatic number of oriented graphs // J. Graph Theory. 1997. V. 25. P. 191-205.

37. Shannon C. E. A theorem on coloring the lines of a network //J. Math, and Phys. 1949. V. 28. P. 148-151.

38. Steinitz E. Polyeder und Raumeinteilungen // Encyclop. math. Wissensch. 1922. V. 3. P. 1-139.

39. Tutte W.T. On the imbedding of linear graphs in surface // Proc. London Math. Soc. 1950. V. 51, №2. P. 474-483.

40. Tutte W.T. A contribution to the theory of chromatic polinomials // Canad. J. Math. 1954. V. 6. P. 80-91.

41. Tutte W.T. Graph theory // Massachusetts e.a.: Addison-Wesley Publ. 1984.

42. Van den Heuvel J., McGuinness S. Colouring the square of a planar graph // Unpublished manuscript. 1999.

43. Vince A. Star chromatic number // J. Graph Theory. 1988. V. 12. P. 551-559.

44. Wegner G. Graphs with given diameter and a coloring problem // Technical Report. University of Dortmund. 1977.

45. Zhu X. Circular chromatic number: a survey // Discrete Math. 2001. V. 229. P. 371-410.

46. Бородин O.B. Доказательство гипотезы Б. Грюнбаума об ациклической 5-раскрашиваемости плоских графов // Доклады АН СССР. 1976. Т. 231. С. 18-20.

47. Бородин О.В. Раскраски и топологические представления графов // Дискрет. анализ и исслед. операций. 1996. Т. 3, .№4. С. 3-27.

48. Бородин О.В., Брусма X., Глебов А. Н., Ван ден Хойвел Я. Минимальные степени и хроматические числа квадратов плоских графов // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8, №4. С. 9-33.

49. Бородин О.В., Иванова А.О. Ориентированная раскраска плоских графов с обхватом не менее 4 // Сибирские Электронные Математические Известия. 2005. Т. 2. С. 239-249.

50. Бородин О.В., Иванова А.О., Косточка A.B. Ориентированная 5-раскраска вершин в разреженных храфа.ч. , t uuu.nü »iраций. Сер. 1. 2006. Т. 1, №1. С. 16-32.

51. Бородин О.В., Иванова А.О., Неустроева Т.К. (p,q)-pacKpacKa разреженных плоских графов // Мат. Заметки ЯГУ. 2006. Т. 13. Вып. 2. С. 3-9.

52. Бородин О.В., Иванова А.О., Неустроева Т.К. О строении младших граней в выпуклых много-гранниках // Мат. заметки ЯГУ. 2006. Т. 13. Вып. 1. С. 29-44.

53. Бородин О.В., Иванова А.О., Неустроева Т.К. Предписанная (p,q)-раскраска разреженных плоских графов // Сибирские Электронные Математические Известия. 2006. Т. 3. С. 355-361.

54. Бородин О.В., Иванова А.О., Неустроева Т.К. 2-дистанционная раскраска разреженных плоских графов // Сибирские Электронные Математические Известия. 2004. Т. 1. С. 76-90.

55. Бородин О.В., Иванова А.О., Неустроева Т.К. Достаточные условия 2-дистанционной (А + 1)-раскрашиваемости плоских графов с обхватом 6 // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12, №3. С. 32-47.