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

Дискретн. анализ и исслед. опер., 2010, том 17, выпуск 5, страницы 22–36 (Mi da622)

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

Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с обхватом не менее 7

А. О. Иванова

Институт математики при Якутском гос. университете, Якутск, Россия

Аннотация: Тривиальная нижняя граница для 2-дистанционного хроматического числа $\chi_2(G)$ любого графа $G$ с максимальной степенью $\Delta$ равна $\Delta+1$. Известны примеры графов со сколь угодно большой $\Delta$ и обхватом $g\le6$, для которых $\chi_2(G)\ge\Delta+2$. В работе улучшены известные ограничения на $\Delta$ и $g$, при которых плоский граф $G$ имеет $\chi_2(G)=\Delta+1$. Ил. 2, библиогр. 24.

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

УДК: 519.17

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



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


© МИАН, 2024