Реберная и тотальная раскраска интервальных графов

Реберной раскраской графа называется приписывание ребрам графа цветов таким образом, что смежные ребра получают разные цвета. Наименьшее число цветов, в которые можно раскрасить ребра графа $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.