Структурные свойства и раскраски плоских графов

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

В настоящей работе решается ряд задач о локальном строении и раскрасках плоских графов. Известно, что ключом к решению многих задач о раскрасках является применение подходящих структурных результатов. Наиболее ярким примером в этом отношении служит полученное в 1976 г. К. Аппелем и В. Хакеном [13, 14, 15] доказательство теоремы о четырех красках, основанное на построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другой пример того же рода — это построенная О. В. Бородиным [5,17, 19] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную ракскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, — ациклический).

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

Недостатком описанного подхода по применению структурных результатов при доказательстве теорем о раскрасках является то, что возникающие системы конфигураций часто оказываются громоздкими и не представляют интереса вне контекста той задачи о раскраске, для решения которой они используются. Начиная со второй половины 20 века в работах таких математиков как А. Лебег [43], А. Коциг [40, 41, 42], Б. Грюнбаум [28, 29, 30], Е. Юцович [35, 36], О. В. Бородин [3, 6, 7, 8, 9, 12, 18, 19, 21, 22] и других теоремы о локальном строении плоских графов (а также графов, вложенных в другие поверхности) начинают выступать в качестве самостоятельного объекта изучения, важного с точки зрения расшифровки структуры плоских графов. В связи с этим особое значение приобретает доказательство неулучшаемых структурных результатов.

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

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

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

Помимо доказательства совершенно новых фактов (теоремы 2.1 и 4.1) в работе доказаны усиления и обобщения результатов, ранее полученных В. А. Аксеновым [2, 12], О. В. Бородиным [12, 18], X. Грецшем [25], Т. Йенсеном [33], А. В. Косточкой [39], А. Коцигом [40], Л. С. Мельниковым [12], И. Г. Перепелица [39], Г. Сабидусси [12], М. Штибицем [12], Б. Тофтом [12], К. Томассеном [33] и другими авторами. Улучшены известные верхние оценки для хроматических чисел квадратов плоских графов [11, 31] и графов пересечений боксов на плоскости [16, 39]. Все приведенные в работе доказательства конструктивны и легко могут быть преобразованы в алгоритмы полиномиальной сложности.

Диссертация состоит из введения, пяти глав, разбитых на разделы и пункты, и списка литературы, включающего 50 наименований. Внутри каждой главы используется своя нумерация теорем, лемм, предложений, следствий, замечаний, формул и рисунков. Все результаты диссертации опубликованы в [3, 4, 7, 8, 9, 10]. Диссертат-нт благодарит всех сотрудников лаборатории теории графов Института математики СО РАН и особенно своего научного руководителя О. В. Бородина за поддержку, оказанную при подготовке диссертации.

1. Аксенов В. А. О продолжении 3-раскраски на плоских графах // Дискретный анализ: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1974. Вып. 26. С. 3−19.

2. Аксенов В. А. Хроматически связные вершины в плоских графах // Методы дискретного анализа в теории управляющих систем: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1977. Вып. 31. С. 5−16.

3. Аксенов В. А., Бородин О. В., Глебов А. Н. Об одном структурном свойстве плоских графов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, № 4. С. 5−19.

4. Аксенов В. А., Бородин О. В., Глебов А. Н. О продолжении 3-раскраски с двух вершин в плоском графе без 3-циклов // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9, № 1. С. 3−26.

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

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

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

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

9. Бородин О. В., Глебов А. Н. О разбиении плоского графа обхвата 5 на пустой и ациклический подграфы //Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8, № 4. С. 34−53.

10. Глебов А. Н. Оценки для числа вырожденности графов пересечений боксов на плоскости в зависимости от обхвата // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9, № 2. С. 3−20.

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

12. Aksenov V. A., Borodin O. V., Mel’nikov L. S., Sabidussi G., Stiebitz M., Toft B. Deeply asymmetric planar graphs // J. of Combin. Theory. Ser. B. (Submitted.).

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

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

15. Appel K., Haken W. The four color proof suffices // Math. Intelligencer. 1986. V. 8, N 1. P. 10−20.

16. Asplund E., Grunbaum B. On a coloring problem // Math. Scand. 1960. Y. 8. P. 181−188.

17. Borodin O. V. On acyclic colorings of planar graphs // Discrete Math. 1979. V. 25, N 3. P. 211−236.

18. Borodin O. V. Joint extension of two Kotzig’s theorems on 3-polytopes // Combinatorica. 1992. V. 13, N 1. P. 121−125.

19. Borodin O. V. Four problems on plane graphs raised by Branko Grunbaum // Contemporary Math. 1993. V. 147. P. 149−156.

20. Borodin O. V. A new proof of Grunbaum’s 3-color theorem // Discrete Math. 1997. V. 169, N 1−3. P. 177−183.

21. Borodin O. V. Triangulated 3-polytopes without faces of low weight // Discrete Math. 1998. V. 186, N 1−3. P. 281−285.

22. Borodin O. V., Woodall D. R. Short cycles of low weight in normal plane maps with minimum degree 5 // Discuss. Math. Graph Theory. 1998. V. 18, N2. P. 159−164.

23. Burling J. P. On coloring problems of families of prototypes // Ph. D. Thesis, University of Colorado, Boulder, CO, 1965.

24. Chartrand G., Kronk H. V. The point-arboricity of planar graphs //J. London Math. Soc. 1969. V. 44, N 4. P. 612−616.

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

26. Griinbaum B. Grotzsch’s theorem on 3-coloring // Michigan Math. J. 1963. V. 10, N 3. P. 303−310.

27. Griinbaum B. Acyclic colorings of planar graphs // Israel J. Math. 1973. V. 14, N 3. P. 390−408.

28. Griinbaum B. Polytopal graphs // Math. Assos. of Amer. Studies in Math. 1975. V. 12. P. 201−204.

29. Griinbaum B. New views on some old questions of combinatorial geometry // Proc. Intern. Colloq. Rome. 1973 / Accademia nacionale dei lincei. Roma. 1976. P. 451−468.

30. Griinbaum B., Shephard G. C. Analogues for tillings of Kotzig’s theorem on minimal weight of edges // Annals of discrete math. 1981. V. 12. P. 129−140.

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

32. Jendrol S., Madaras T., Sotak R., Tuza Z. On light cycles in plane triangulations // Discrete Math. 1999. V. 197/198. P. 453−467.

33. Jensen T. R., Thomassen C. The color space of a graph // J. Graph Theory. 2000. V. 34, N 3. P. 234−245.

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

35. Jucovic E. Strengthening of a theorem about 3-polytopes // Geom. dedicata. 1974. V. 13. P. 20−34.

36. Jucovic E. Convex 3-polytopes // Veda. Bratislava. 1981.

37. Kostochka A. V., Melnikov L. S. Note to the paper of Griinbaum on acyclicrnlor-Ws // «DisrrPtP MfltTi 107» V 14 N4 P 4n3−4Q6 ————0″ ! ! ———————-. ..^. .

38. Kostochka A. V., NeSetfil J. Coloring relatives of intervals on the plane, I: chromatic number versus girth // European J. Combin. 1998. V. 19, N 1. P. 103−110.

39. Kostochka A. V., Perepelitsa I. G. Coloring triangle-free intersection graphs of boxes on the plane // Discrete Math. 2000. V. 220, N 1−3. P. 243−249.

40. Kotzig A. Contribution to the theory of Eulerian polyhedra // Mat. Casopis. 1955. V. 5, P. 101−113.

41. Kotzig A. From the theory of Euler’s polyhedrons // Mat. Casopis. 1963. V. 13, P. 20−34.

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

43. Lebesgue H. Quelques cosequences simple de la formule d’Euler //J. math, pure applic. 1940. Y. 9, P. 27−43.

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

45. Stein S. K. B-sets and coloring problems // Bull. Amer. Math. Soc. 1970. V. 76, N 4. P. 805−806.

46. Stein S. K. B-sets and planar maps // Pacific J. Math. 1971. V. 37, N 1. P. 217−224.

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

48. Thomassen C. Decomposing planar graphs // Technical report. The Technical University of Denmark, 1993.

49. Wegner G. Note on a paper of B. Grunbaum on acyclic colorings // Israel J. Math. 1973. V. 14, N 4. P. 409−412.

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