Строение младших граней и (P, Q)-раскраски плоских графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ р ц ПД ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева Н

ООЗОБ2155

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

Неустроева Татьяна Кимовна

СТРОЕНИЕ МЛАДШИХ ГРАНЕЙ И (Р, (З)-РАСКРАСКИ ПЛОСКИХ ГРАФОВ

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

АВТОРЕФЕРАТ

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

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

003052155

Работа выполнена в Институте математики им. С. Л. Соболева СО РАН и НИИ математики при Якутском государственном университете.

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

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

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

Защита состоится " апреля 2007 г. в 16 часов на засе-

дании диссертационного совета Д 003.015.01 в Институте математики им. С. Л. Соболева СО РАН по адресу: пр. Коптюга 4, 630090, г. Новосибирск.

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

Автореферат разослан " Э " марта 2007 г.

Ученый секретарь диссертационного совета,

д. ф.-м. н. ¡/¡¡л Ю. В. Шамардин

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

Актуальность темы. Задачи раскраски графов интересуют многих специалистов не только по теории графов и дискретной математике, но и физиков, программистов, экономистов и других. Этот интерес вызван тем, что задачи о раскрасках графов имеют разнообразные приложения, в частности, в задаче назначения радиочастот в сетях мобильного телефонирования, в задаче оптимальной организации структуры баз данных, распределения ресурсов, в задачах, возникающих при планировании производства, составлении графиков осмотра и хранения товаров и т. д.

Наиболее широко известной из задач раскраски графов является знаменитая проблема четырех красок (1852 г.): требуется доказать возможность раскрасить плоскую карту четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Доказательство было дано более чем через 120 лет К. Аппелем и В. Хакеном. Решение состояло в построении так называемой "неизбежной системы сводимых конфигураций", а именно в нахождении такой системы структурных фрагментов, что хотя бы один из них содержится в каждом графе рассматриваемого класса, причем каждая из этих конфигураций является сводимой, т. е. должна отсутствовать в минимальном контрпримере к данной задаче о раскраске. Метод сводимых конфигураций применяется для решения подавляющего большинства задач раскраски плоских графов. Наиболее полную информацию о результатах в области раскраски графов, полученных до середины 90-х годов прошлого столетия, можно найти в книге В. Тофта и Т. Р. Йенсена [7].

Отметим, что первоначально большинство фактов о строении плоских графов, установленных при решении задач о раскрасках, использовались только в рамках рассматриваемой задачи, т. е. интерес к локальным свойствам графов возникал только применительно к задачам раскраски. Один из первых шагов в изучении структуры плоских графов был сделан А. Лебегом в 1940 г. Созданная А. Лебегом [9] теория эйлеровых вкладов, основанная на преобразовании известной формулы Эйлера для

многогранников, в дальнейшем получила широкое применение и развитие в работах А. Коцига [8], Б. Грюнбаума [6] и других. Последующие важные шаги в становлении структурной теории плоских графов были сделаны О. В. Бородиным, в частности, в [1] - [5]. Перечисленные, а также и многие другие, работы по раскраскам плоских графов позволили теоремам о строении плоских графов выступить уже в роли самостоятельного объекта изучения, заложив основу структурной теории плоских графов. Введение в эту теорию представлено в докторской диссертации О. В. Бородина [1].

Заметим, что структурные теоремы, полученные в перечисленных выше работах, касаются плоских графов с минимальной степенью <5^3. Что же касается плоских графов с 5 = 2, то, хотя об их строении известно довольно много, стройной классификации этих графов в настоящее время пока нет. Интерес к изучению строения плоских графов с 6 — 2 вызван возможностью применения структурных свойств этих графов к некоторым видам раскраски графов, в частности, реберной, тотальной, 2-дистанционной, (р, д)-раскраске, ориентированной, предписанной и других.

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

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

нии 2 — не менее чем на д. Поскольку частоты близко расположенных источников должны различаться сильнее ввиду интерференции волн, то р ^ д.

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

важному частному случаю этой раскраски — 2-дистанционной.

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

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

1. Уточнен один из параметров теоремы Бородина (2002 г.), усиливающей теорему Лебега (1940 г.) о строении младших граней 3-многогранников.

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

3. В дополнение к результатам п. 2, при д — 6 найден класс 2-дистанционно (А + 1)-раскрашиваемых плоских графов; они имеют Д ^ 31, а каждое ребро в них инцидентно вершине степени 2.

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

В диссертацию включены лишь те результаты совместных работ [12] - [20], которые получены диссертантом.

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

Апробация работы. Результаты работы докладывались в 2006 г. на X Лаврентьевских чтениях Республики Саха (Якутия) и IV Всероссийской школе-семинаре студентов, аспирантов, молодых ученых и специалистов "Математическое моделирование развития северных территорий РФ"и подробно обсуждались на научном семинаре лаборатории теории графов Института математики СО РАН в 2004-2006 гг. Работа автора по раскраске плоских графов в 2005-2007 гг. поддержана грантом РФФИ 05-

01-00816. Автор в 2006 г. за работу по теме диссертации получил Государственную стипендию Республики Саха (Якутия) для молодых ученых и аспирантов.

Публикации. По теме диссертации опубликованы 9 работ (включая 7 журнальных статей и одну статью в трудах конференции X Лаврентьевских чтений).

Структура и объем диссертации. Диссертация изложена на 78 страницах и состоит из введения, трех глав и библиографии, содержащей 45 наименований.

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

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

Первая глава посвящена изучению структуры эйлеровых многогранников, называемых далее 3-многогранниками, а именно строению их младших граней (ограниченных не более чем 5 ребрами). Э. Штейницем установлено, что 3-связные плоские графы взаимно однозначно соответствуют 3-многогранникам.

Будем говорить, что грань / = ,..., уг ранга г (длина граничного цикла грани) имеет тип (¿2,... ,йг), где й{ < ¿г+\ при каждом г, 1 < г < г — 1, если г-я по величине степень вершины среди вершин, инцидентных грани /, не превосходит й{, 1 <г<г.

В 1940 г. А. Лебег [9] показал, что любой 3-многогранник содержит грань одного из следующих типов:

(3,6, оо), (3,7,41), (3,8,23), (3,9,17), (3,10,14), (3,11,13),

(4,4, оо), (4,5,19), (4,6,11), (4,7,9), (5,5,9), (5,6,7), (3,3,3, оо), (3,3,4,11), (3,3,5,7), (3,4,4,5), (3,3,3,3,5).

Некоторые параметры этого описания позднее были уточнены для отдельных классов 3-многогранников. Но вплоть до работы [3] (2002 г.) ни один из этих параметров не был улучшен без ухудшения других ее параметров. О. В. Бородин в [3] улучшил девять параметров теоремы Лебега без ухудшения остальных.

Теорема (Бородин, [3]). Каждый 3-многогранник содержит грань одного из следующих типов:

(3,6, оо*), (3,8*,22), (3,9*, 15), (3,10*, 13), (3,11*, 12), (4,4,оо*), (4,5*, 17), (4,6*, И), (4, 7*, 8), (5,5*,8), (5,6,6*), (3,3,3, оо*), (3,3,4*, 11), (3,3,5*, 7), (3,4,4,5*), (3,3,3,3,5*).

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

В [3] была поставлена задача: найти уточнение теоремы Лебега, не допускающее дальнейших усилений. Заметим, что решение этой задачи требует уточнения небольшого числа параметров. В диссертации сделан один шаг в этом направлении, а именно член (4,5,17) заменяется на (4,5,16).

Во второй главе представлены результаты о 2-дистанционной раскраске разреженных плоских графов.

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

Существует гипотеза Г. Вегнера (1977 г.) [11] о том, что Х2(£) ^ [|Д(С?)] +1 для любого плоского графа С? с максимальной степенью А (С). Первый результат в этом направлении был получен Я. Ван-ден-Хойвелом и С. Мак Гиннессом [10], доказавшим что Х2(б) ^ 2Д + 25. В [2} О. В. Бородин, А.Н. Глебов, X. Брусма и Я. Ван-ден-Хойвел доказали, что для произвольных плоских графов Х2{&) < [|Д(<?)1+1 при Д(С) > 47, что улучшило оценку Г. Агнарсона и М.М. Холдорсона: <

[§Д((7)]+2 при Д(С) ^ 749.

Для любого графа С с максимальной степенью Д очевидной нижней оценкой для Х2 является Д+1, так как Д+1 есть необходимое число цветов для 2-дистанционной раскраски Д-звезды, содержащейся в любом графе. В частности, эта оценка достигается на всех деревьях, но не достигается, например, на циклах Сз)*+\- Обхватом <7((?) графа С? называется наименьшая длина цикла в С. Вопрос о том для сколь малых д можно гарантировать равенство Хг(<3!) = Д + 1 путем наложения ограничения только на Д был полностью решен в [12, 13].

Результаты, включенные в диссертацию из работ [12, 13], получены диссертантом и представлены в виде теоремы 2.1.

Теорема 2.1. Пусть (? — планарный граф, тогда Х2(С) — А + 1 в каждом из следующих случаев: ([) А = А и д ^ 15; (и) Д = 5 и д ^ 13; (ш) Д = 6 и д ^ 12; (г\г) Д ^ 7 и д ^ И; (V) Д ^ 9 и д = 10; (лп) Д ^ 16 и д = 9; (ун) Д ^ 30 и д = 7.

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

В [13] было показано существование плоских графов с д ^ 6, для которых Х2 > Д + 1 пРи произвольно большом Д. Таким образом, определенное нами условие на обхват, д ^ 7, является неулучшаемым для 2-дистанционной (Д + 1)-раскрашивамости плоского графа. При этом доказательство утверждения (уп) в теореме 2.1 было технически наиболее сложным.

Ввиду сказанного в предыдущем абзаце для обеспечения 2-дистанционной (Д + 1)-раскрашиваемости плоского графа С? обхвата 6 потребовалось ввести дополнительное структурное требование: хотя бы один из концов каждого ребра графа С? является вершиной степени 2. В [14] было доказано, что если <9 — плоский граф обхвата 6, в котором Д(С) ^ 179, а каждое ребро инцидентно 2-вершине, то = Д(С) + 1. В диссертации этот

результат был усилен следующим образом.

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

Д(С) +1.

Третья глава содержит результаты о (р, q)- и предписанной (р, д)-раскрасках плоских графов достаточно большого обхвата.

Раскраска вершин графа О называется (р, д)-раскраской, ес-

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

писанное (р, дихроматическое число Хр^С*?).

Понятно, что ранее рассмотренная 2-дистанционная раскраска является в точности (1, 1)-раскраской.

Для (р,р)-хроматического числа произвольного графа (3 имеем очевидную нижнюю оценку: Хр,р{@) ^ Ар + 1 (из тех же соображений, что и для (1, 1)-раскраски). Заметим, что всегда Хр,р(@) < V ■ XI,1 ~Р + 1, так как минимальную (1,1)-раскраску цветами 0,1,..., Х1,1 — 1 можно преобразовать, умножением всех ее цветов на р, в (р, р)-раскраску цветами 0, р,..., (хгд — 1)р. Поэтому ввиду теоремы 2.1 можно утверждать, что если б — плоский граф обхвата не менее 7, то Хр,р(@) — Ар + 1 при Д ^ 30.

Для плоского графа О. В. Бородин, А. Н. Глебов, X. Врусма и Я. Ван-ден-Хойвел [2] доказали, что Хр,д(С') ^ Юр + с, где с — величина, не зависящая от р, а для разреженного плоского графа при р > д ^ 1 справедлива доказываемая в диссертации

Теорема 3.1. Пусть О — планарный граф обхвата не менее 31. Тогда хм(<?) < 2р + (А(С) - 1)(2д - 1) при Д(в) > 5.

Ясно, что при р > д данная оценка лучше той, что приведена выше для р — д. Что касается нижней оценки (р, дихроматического числа, то доказано

Предложение 3.2. Существуют такие плоские графы (7 произвольного обхвата со сколь угодно большим Д, что ХР,,(С)>2р + 1 + (Д-2)?.

Таким образом, при д главный член, равный 2р, в теореме 3.1 не допускает улучшения.

Очевидно, что Хр,д(<3) ^ Хр,д(&) Для любого графа О. При а — О величина 0 может сколь угодно сильно отличаться от Хр,ч(0).

Предложение 3.3. Для любого п ^ 1 существует граф б такой, что Хр,о(С) = Р + 1, а Хр)0(<?) > п(2р ~ !)•

Что касается предписанных (р, д)-раскрасок при д ^ 1, то вопрос о существовании графа (3, для которого Ф остается открытым. Для произвольных плоских графов в [2] доказана та же оценка: Хр,д(С?) ^ Юр + с, что и для хр>д((7). Для предписанного (р, дихроматического числа в диссертации доказывается та же верхняя оценка, что и для обычной (р, д)-раскраски, а именно

Теорема 3.4. Пусть С — планарный граф обхвата не менее

5(Г<а(о&)(ц-1)1+4) + 1. Тогдах1Р,д(0) < 2р+(Д(С)-1)(2д-1)

при Д((?) ^ 4.

Отметим, что ограничение на обхват в теореме 3.4, в отличие от теоремы 3.1, является растущей функцией от р при фиксированных д и Д((?). Следующий факт частично объясняет это обстоятельство.

Предложение 3.5. В задаче предписанной (р, д)-раскраски в 2р+(Д((7) —1)(2д—1) цветов к-цепъ, где к < 1,

не является сводимой конфигурацией при Д(С?) ^ 2.

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

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

Список литературы

[1] Бородин О. В. Строение и раскраска плоских графов: Дис. ... док.физ.-мат.наук: 01.01.09. Новосибирск. 1994. 239 с.

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

[3] Бородин О. В. Усиление теоремы Лебега о строении младших граней в выпуклых многогранниках // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9, № 3. С. 29-39.

[4] Borodin O.V. Cyclic degree and cyclic coloring of S-polytopes // J. Graph Theory. 1996. Vol. 23, № 3. P. 225-231.

[5] Borodin O.V. Triangulated 3-polytopes without faces of low weight // Discrete Math. 1998. Vol. 186. P. 281-286.

[6] Grunbaum B. Acyclic coloring of planar graphs // Israel J. Math. 1973. Vol. 14, № 3. P. 390-408.

[7] Jensen T.R., Toft B. Graph coloring problems. New York: John Wiley & Sons, Jnc., 1995.

[8] Kotzig A. Contribution to the theory of Eulerian polyhedra // Mat. Casopis. 1955. Vol. 5. P. 101-113.

[9] Lebesque H. Quelques consequences simples de la formule d'Euler // J. Math. Pures Appl. 1940. Vol.9. P. 27-43.

[10] Van den Heuvel J., McGuinness S. Coloring the square of planar graph // Unpublished manuscript. 1999.

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

Работы автора по теме диссертации

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

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

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

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

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

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

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

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

[20] Иванова А.О., Неустроева Т.К. О (р,д)-раскраске разреженных плоских графов //IV Всероссийская школа-семинар студентов, аспирантов, молодых ученых и специалистов "Математическое моделирование развития северных территорий РФ": Тез. докл. Якутск: Филиал изд-ва ЯГУ. 2006. С. 38-40.

Неустроева Татьяна Кимовна

Строение младших граней и (р, д)-раскраски плоских графов

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

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

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

Введение.

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

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

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

1. Строение младших граней эйлеровых многогранников

1.1. Формулировка основного результата главы

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

2. 2-дистанционная раскраска плоских графов

2.1. Обзор результатов главы

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

2.2.1. Случай д ^

2.2.2. Случай д =

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

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

2.3.2. Окончательное распределение зарядов и его следствия

3. Задача (р, д)-раскраски плоских графов.

3.1. Обзор результатов главы

3.2. Доказательство результатов о (р, <?)-раскраске

3.3. Доказательство результатов о предписанной (р, г/)-раскраскс

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

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

Наиболее широко известной из задач раскраски графов является знаменитая проблема четырех красок (1852 г.): требуется доказать возможность раскрасить плоскую карту четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Доказательство было дано более чем через 120 лет К. Аппелем и В. Хакеном [12, 13, 14]. Решение состояло в построении так называемой "неизбежной системы сводимых конфигураций", а именно в нахождении такой системы структурных фрагментов, что хотя бы один из них содержится в каждом графе рассматриваемого класса, причем каждая из этих конфигураций является сводимой, т. е. должна отсутствовать в минимальном контрпримере к данной задаче о раскраске. Метод сводимых конфигураций применяется для решения подавляющего большинства задач раскраски плоских графов. Наиболее полную информацию о результатах в области раскраски графов, полученных до середины 90-х годов прошлого столетия, можно найти в книге В. Тофта и Т. Р. Йенсена [25].

Отметим, что первоначально большинство фактов о строении плоских графов, установленных при решении задач о раскрасках, использовались только в рамках рассматриваемой задачи, т. е. интерес к локальным свойствам графов возникал только применительно к задачам раскраски. Один из первых шагов в изучении структуры плоских графов был сделан А. Лебегом в 1940 г. Созданная А. Лебегом [30] теория эйлеровых вкладов, основанная на преобразовании известной формулы Эйлера для многогранников, в дальнейшем получила широкое применение и развитие в работах

А. Коцига [27]-[29], Б. Грюнбаума [21]-[23] и других. Последующие важные шаги в становлении структурной теории плоских графов были сделаны О. В. Бородиным, в частности, в [7, 9, 10, 8,19]. Перечисленные, а также и многие другие работы по раскраскам плоских графов позволили теоремам о строении плоских графов выступить уже в роли самостоятельного объекта изучения, заложив основу структурной теории плоских графов. Введение в эту теорию представлено в докторской диссертации О. В. Бородина [7].

Заметим, что структурные теоремы, полученные в перечисленных выше работах, касаются плоских графов с минимальной степенью <5^3. Что же касается плоских графов с 6 = 2, то, хотя об их строении известно довольно много, стройной классификации этих графов в настоящее время пока нет. Интерес к изучению строения плоских графов с 5 = 2 вызван возможностью применения структурных свойств этих графов к некоторым видам раскраски графов, в частности, реберной, тотальной, 2-дистанционной, (р, д)-раскраске, ориентированной, предписанной и других.

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

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

Цель настоящей работы состоит в получении новых результатов о строении младших граней в 3-многогранниках и (р, (^-раскраске (в том числе и предписанной) разреженных плоских графов, причем в диссертации большое внимание уделяется наиболее важному частному случаю этой раскраски — 2-дистанционной,

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

Основные результаты диссертации:

1. Уточнен один из параметров теоремы Бородина (2002 г.), усиливающей теорему Лебега (1940 г.) о строении младших граней 3- многогранников.

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

3. В дополнение к результатам п. 2, при д = 6 найден класс 2-дистапциошю (Д + 1)-раскрашиваемых плоских графов; они имеют Д ^ 31, а каждое ребро в них инцидентно вершине степени 2.

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

В диссертацию включены лишь те результаты совместных работ [37] - [45], которые получены диссертантом.

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

По теме диссертации опубликованы 7 журнальных статей [37, 38, 39, 41, 42, 43, 44], одна статья в трудах конференции [40] и заметка в сборнике докладов [45].

Диссертация состоит из введения, трех глав и библиографии, содержащей 45 наименований.

1. Августинович С. В., Бородин O.B. Окрестности ребер в нормальных картах // Дискретный анализ и исследование операций. 1995. Т. 2, № 3. С. 3-9.

2. Бородин О. В. Решение задач Коцига и Грюнбаума об отделимости цикла в плоском графе // Мат. заметки. 1989. Т. 46, выи. 5. С. 9-12.

3. Бородин О. В. Оценки для числа легких ребер в плоских графах. Новосибирск, 1989. 12 С. (Препринт / АН СССР Сиб. отделение Ип-т математики; Л'1-' 6.)

4. Бородин О. В. Совместное обобщение теорем Лебега и Кои,ига о комбинаторике плоских карт // Дискретная математика. 1991. Т. 3, вып. 4. С. 24-27.

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

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

7. Бородин О. В. Строение и раскраска плоских графов: Дис. . док.физ-мат.наук: 01.01.09. Новосибирск. 1994. 239 с.

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

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

10. Бородин О. В. Усиление теоремы Лебега о строении младших граней в выпуклых многогранниках II Дискретный анализ и исследование операций. Сер. 1. 2002. Т. 9, № 3. С. 29-39.

11. Agnarsson G., Halldorsson М. М. Coloring powers of planar graphs // Unpublished manuscript. 2000.

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

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

14. Appel K., Haken W. The four color proof suffices 11 Math. Intelligencer. 1986. Vol.8, № 1. P. 10-20.

15. Borodin O.V. An extention of Kotzig's theorem on the minimum weight of edges in Z-polytopes // Math. Slovaca. 1992. Vol.42, № 4. P. 385-389.

16. Borodin O.V. Joint extension of two theorems of Kotzig on Z-polytopes // Combinatorica. 1993. Vol. 13, № 1. P. 121-125.

17. Borodin 0. V. Cyclic degree and cyclic coloring of 3-polytopes //J. Graph Theory. 1996. Vol. 23, № 3. P. 225-231.

18. Borodin O. V. More about the weight of edges in planar graphs // Tatra Mountains Math. Publ. 1996. V. 9. P. 11-14.

19. Borodin O.V. Triangulated Z-polytopes without faces of low weight, // Discrete Math. 1998. Vol. 186, N 1-3. P. 281-286.

20. Borodin O.V., Woodall D.R. Cyclic degree of Z-polytopes // Graphs and Combinatorics. 1999. Vol. 15, № 3. P. 267-277.

21. Griinbaum B. Acyclic coloring of planar graphs // Israel J. Math. 1973. Vol.14, № 3. P. 390-408.

22. Griinbaum B. New views on some old questions of combinatorial geometry / /' Proc. Intern. Colloq. Rome, 1973 / Accademia Nacionale dei Lincei. 1976. P. 451-468.

23. Griinbaum B., Shephard G.C. Analogues for tillings of Kotzig's theorem on minimal weight of edges // Annals of Discrete Math. 1981. Vol. 12. P. 129-140.

24. Horna'k M., Jendrol' S. Unavoidable sets of face types for planar maps // Discus. Math. Graph Theory. 1996. Vol. 16, № 2. P. 123-142.

25. Jensen T.R., Toft В. Graph coloring problems. New York: .John Wiley к Sons, Jnc., 1995.

26. Jucovic E. Strengthening of a theorem about 3-polytopes // Geometriae Dedicata. 1974. Vol.3. P. 233-237.

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

28. Kotzig A. From the theory of Euler's polyhedrons // Mat. Casopis. 1963. Vol.3. P. 20-34.

29. Kotzig A. Extremal polyhedral graphs // Proc. Second Intern. Conf. on Combin. New York: New York Acad, of sei., 1979. P. 569-570.

30. Lebesque H. Quelques consequences simples de la formale, d'Etiler // .]. Math. Pures Appl. 1940. Vol.9. P. 27-43.

31. Ore O., Plummer M.D. Cyclic coloration of plane graphs // Recent Progress in Combinatorics. New York: Acad. Press, 1969. P. 287-293.

32. Plummer M.D., Toft B. Cyclic coloration of 3-polytopes // J. Graph Theory. 1987. Vol. 11, N 4. P. 507-515.

33. Shannon С. E. A theorem on coloring the lines of a network //' J. Math, and Pliys. 1949.V. 28. P. 148-151.

34. Steinitz E. Polyheder und Raumeinteilungen // Enzykl. math. Wiss. 1922. Vol. ЗАВ (Geometrie), N 12. P. 1-139.

35. Van den Heuvel J., McGuinness S. Coloring the square, of planar graph '/ Unpublished manuscript. 1999.

36. Wegner G. Graphs with given diameter and a coloring problem // Technical Report. University of Dortmund. 1977.Работы автора по теме диссертации

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

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

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

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

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

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

43. Бородин О.В., Иванова А.О., Неустроева Т.К. Достаточные условия 2-дистанционной (Д + 1 )-раскрашиваемости плоских графов с обхватом 6 // Сибирские Электронные Математические Известия. 2006. Т. 3. С. 441-450.