Том 5, серия 1, номер 4, 1998 г., Стр. 18-24

УДК 519.1
В. А. Бояршинов
Реберная и тотальная раскраска интервальных графов

Аннотация:
Реберной раскраской графа называется приписывание ребрам графа цветов таким образом, что смежные ребра получают разные цвета. Наименьшее число цветов, в которые можно раскрасить ребра графа $G$, называется хроматическим индексом графа $G$ и обозначается через $\chi'(G)$. Говорят, что $G$ принадлежит классу 1, если $\chi'(G)=\Delta(G)$, где $\Delta(G)$ – степень графа $G$; иначе $G$ принадлежит классу 2. Тотальной раскраской графа называется приписывание вершинам и ребрам графа цветов таким образом, чтобы смежные или инцидентные элементы получили разные цвета. Наименьшее число цветов, в которые можно тотально раскрасить граф $G$, называется тотальным хроматическим числом $G$ и обозначается через $\chi_T(G)$. Говорят, что $G$ принадлежит типу 1, если $\chi_T(G)=\Delta(G)+1$; $G$ принадлежит типу 2, если $\chi_T(G)=\Delta(G)+2$. В данной работе рассматривается проблема классификации интервальных графов. Доказано, что любой интервальный граф с нечетной максимальной степенью вершин принадлежит классу 1 и его ребра могут быть раскрашены в минимальное число цветов алгоритмом, временная сложность которого не превосходит $O(|V_G|+|E_G|+(\Delta(G))^2)$. Затем показано, что для интервальных графов выполняется предположение Бехзада и Визинга о том, что $\chi_T(G)\leqslant\Delta(G)+2$. Кроме того, доказано, что любой интервальный граф с четной максимальной степенью вершин принадлежит типу 1 и его элементы могут быть раскрашены в минимальное число цветов алгоритмом, временная сложность которого не превышает $O(|V_G|+|E_G|+(\Delta(G))^2)$.
Библиогр. 15.

Бояршинов В. А. ¹
1. Институт систем информатики СО РАН,
пр. Лаврентьева, 6, 630090 Новосибирск, Россия

Статья поступила 18 марта 1998 г.
Исправленный вариант — 18 сентября 1998 г.