RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2005, том 12, выпуск 3, страницы 32–47 (Mi da70)

Эта публикация цитируется в 12 статьях

Достаточные условия 2-дистанционной $(\Delta+1)$-раскрашиваемости плоских графов с обхватом 6

О. В. Бородинa, А. О. Ивановаb, Т. К. Неустроеваb

a Институт математики им. С. Л. Соболева СО РАН
b Якутский государственный университет им. М. К. Аммосова

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

УДК: 519.71

Статья поступила: 22.12.2004
Переработанный вариант: 13.06.2005



Реферативные базы данных:


© МИАН, 2024