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 г.

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