Том 12, серия 1, номер 3, 2005 г., Стр. 32-47

УДК 519.71
О. В. Бородин, А. О. Иванова, Т. К. Неустроева
Достаточные условия 2-дистанционной $(\Delta+1)$-раскрашиваемости плоских графов с обхватом 6

Аннотация:
Для 2-дистанционного хроматического числа графа $G$ с максимальной степенью $\Delta$ нижняя граница равна $\Delta+1$. Известно, что если $G$ планарен, а его обхват не меньше 7, то при достаточно большой $\Delta$ эта оценка достигается, но при обхвате 6 это не так. В статье доказано, что если граф $G$ с обхватом 6 планарен, каждое его ребро инцидентно вершине степени 1 или 2, а $\Delta\geqslant 179$, то $\chi_2(G)=\Delta+1$.

Бородин О. В. ¹
Иванова А. О. ²
Неустроева Т. К. ²
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Якутский государственный университет им. М. К. Аммосова, Институт математики и информатики,
ул. Кулаковского, 48, 677000 Якутск, Россия
е-mail: brdnoleg@math.nsc.ru, shmgnanna@mail.ru, podn2001@mail.ru

Статья поступила 27 декабря 2004 г.
Исправленный вариант — 13 июля 2005 г.