Число гармоническое хроматическое

Материал из WikiGrapp
Перейти к:навигация, поиск

Число гармоническое хроматическое (Harmonious chromatic number) — наименьшее целое \,k такое, что существует гармоническая \,k-раскраска, т.е. раскраска вершин \,k цветами такая, что смежные вершины получают разные цвета и для всех i, \, j,\,1 \leq i < j \leq k, существует не более одного ребра с концами, окрашенными цветами \,i и \,j. Это число было введено Франком, Харари, Плансолтом в 1982 г.

Литература

  • Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.