EN|RU

Том 18, номер 2, 2011 г., Стр. 18-28

УДК 519.17
Бородин О. В., Иванова А. О.
2-Дистанционная 4-раскраска плоских субкубических графов

Аннотация:
Тривиальная нижняя граница для 2-дистанционного хроматического числа $\chi_2(G)$ любого графа $G$ с максимальной степенью $\Delta$ равна $\Delta+1$. Известно, что $\chi_2=\Delta+1$, если обхват $g$ не меньше 7, а $\Delta$ достаточно велико. Существуют примеры графов со сколь угодно большой $\Delta$ и обхватом $g\le6$, для которых $\chi_2(G)\ge\Delta+2$. В статье доказана 4-раскрашиваемость плоских субкубических графов с $g\ge23$, что усиливает аналогичный результат О. В. Бородина, А. О. Ивановой и Т. К. Неустроевой (2004) и Дворжака, Шкрековски и Танцера (2008) для $g\ge24$.
Ил. 2, библиогр. 20.

Ключевые слова: плоский граф, 2-дистанционная раскраска, субкубический граф.

Бородин Олег Вениаминович 1,2
Иванова Анна Олеговна 3

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
3. Институт математики при Якутском гос. университете, Якутский гос. университет,
ул. Кулаковского, 48, 677891 Якутск, Россия
е-mail: brdnoleg@math.nsc.ru, shmgnanna@mail.ru

Статья поступила 14 октября 2010 г.

Литература

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

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

[3] Бородин О. В., Иванова А. О., Неустроева Т. К. 2-дистанционная раскраска разреженных плоских графов // Сиб. электрон. мат. изв. — 2004. — № 1. — C. 76–90. (http://semr.math.nsc.ru/)

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

[5] Бородин О. В., Иванова А. О., Неустроева Т. К. Достаточные условия минимальной 2-дистанционной раскрашиваемости плоских графов с обхватом 6 // Сиб. электрон. мат. изв. — 2006. — № 3. — C. 441–450. (http://semr.math.nsc.ru/)

[6] Бородин О. В., Глебов А. Н., Иванова А. О., Неустроева Т. К., Ташкинов В. А. Достаточные условия 2-дистанционной ($\Delta + 1$)-раскрашиваемости плоских графов // Сиб. электрон. мат. изв. — 2004. — № 1. — C. 129–141. (http://semr.math.nsc.ru/)

[7] Иванова А. О. Предписанная 2-дистанционная ($\Delta + 1$)-раскраска плоских графов с обхватом не менее 7 // Дискрет. анализ и исслед. операций. — 2010. — T. 17, № 5. — C. 22–36.

[8] Иванова А. О., Соловьева А. С. 2-Дистанционная ($\Delta + 2$)-раскраска разреженных плоских графов с $\Delta + 3$ // Мат. заметки ЯГУ. — 2009. — T. 16, № 2. — C. 32–41.

[9] Agnarsson G., Halldorsson M. M. Coloring powers of planar graphs // Proc. 11th annual ACM-SIAM symposium on discrete algorithms (San Francisco, CA, 2000). — New York: ACM Press, 2000. — P. 654–662.

[10] Agnarsson G., Halldorsson M. M. Coloring powers of planar graphs // SIAM J. Discrete Math. — 2003. — Vol. 16, N 4. — P. 651–662.

[11] Borodin O. V., Ivanova A. O. 2-Distance ($\Delta + 2$)-coloring of planar graphs with girth six and $\Delta + 18$ // Discrete Math. — 2009. — Vol. 309. — P. 6496–6502.

[12] Borodin O. V., Ivanova A. O. List 2-distance ($\Delta + 2$)-coloring of planar graphs with girth six // Europ. J. Combin. — 2009. — Vol. 30. — P. 1257–1262.

[13] Dvo$\check{r}$ák Z., Kràl D., Nejedl$\grave{y}$ P., $\check{S}$krekovski R. Coloring squares of planar graphs with girth six // Europ. J. Combin. — 2008. — Vol. 29, N 4. — P. 838–849.

[14] Dvo$\check{r}$ák Z., $\check{S}$krekovski R., Tancer M. List-coloring squares of sparse subcubic graphs // SIAM J. Discrete Math. — 2008. — Vol. 22, N 1. — P. 139–159.

[15] Havet F. Choosability of square of planar subcubic graphs with large girth // Discrete Math. — 2009. — Vol. 309. — P. 3353–3563.

[16] Jensen T., Toft B. Graph coloring problems. Wiley-interscience series on discrete mathematics and optimization. A Wiley-interscience publication. — New York: John Willey & Sons, 1995. — XXII+295 p.

[17] Molloy M., Salavatipour M. R. Frequency channel assignment on planar networks // Proc. ESA’02. — London: Springer-Verl., 2002. — P. 736–747. (Lect. Notes Comput. Sci.; Vol. 2461.)

[18] Molloy M., Salavatipour M. R. A bound on the chromatic number of the square of a planar graph // J. Combin. Theory. Ser. B. — 2005. — Vol. 94. — P. 189–213.

[19] Montassier M., Raspaud A. A note on 2-facial coloring of plane graphs // Inform. Process. Lett. — 2006. — Vol. 98, N 6. — P. 235–241.

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

 © Институт математики им. С. Л. Соболева, 2015