Ориентированная и 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. 179 182.

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. nu «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.