В теории графов гармоническая раскраска — это (правильная) раскраска вершин, при которой любая пара цветов появляется на смежных вершинах не более одного раза. Гармоническое хроматическое число χH(G) графа G — это минимальное число цветов, необходимых для гармонической раскраски графа G.
Любой граф обладает гармонической раскраской, поскольку достаточно раскрасить каждую вершину в свой цвет. Таким образом, χH(G) ≤ |V(G)|. Ясно, что существуют графы G с χH(G) > χ(G) (где χ — хроматическое число). Примером может служить путь длины 2, вершины которого можно раскрасить двумя цветами, но нет гармонической раскраски с 2 цветами.
Некоторые свойства χH(G): χH(Tk,3) = ⌈(3/2)(k+1)⌉, где Tk,3 — это полное k-арное дерево с 3 уровнями. (Mitchem 1989)
Гармоническая раскраска была впервые предложена Харари и Плантхолт (Harary, Plantholt, 1982). Мало что известно об этом типе раскраски.
См. также Полная раскраска Гармоническая разметка
Литература
Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
Ссылки A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
Категория:Теория графов Категория:Раскраска графа