Том 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 г.
