Том 17, номер 5, 2010 г., Стр. 22-36
УДК 519.17
Иванова А. О.
Предписанная 2-дистанционная (Δ + 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-дистанционная раскраска, предписанная раскраска.
Иванова Анна Олеговна 1
1. Институт математики при Якутском гос. университете,
ул. Белинского, 58, 677891, Якутск, Россия
е-mail: shmganna@mail.ru
Статья поступила 2 февраля 2010 г.
Исправленный вариант — 28 июля 2010 г.
|