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

Дискретн. анализ и исслед. опер., 2011, том 18, выпуск 2, страницы 18–28 (Mi da643)

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

2-дистанционная 4-раскраска плоских субкубических графов

О. В. Бородинab, А. О. Ивановаc

a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
b Новосибирский гос. университет, Новосибирск, Россия
c Институт математики при Якутском гос. университете, Якутский гос. университет, Якутск, Россия

Аннотация: Тривиальная нижняя граница для 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-дистанционная раскраска, субкубический граф.

УДК: 519.17

Статья поступила: 14.10.2010


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2011, 5:4, 535–541

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


© МИАН, 2024