Гармоническая раскраска

В теории графов гармоническая раскраска — это (правильная) раскраска вершин, при которой любая пара цветов появляется на смежных вершинах не более одного раза. Гармоническое хроматическое число χ_H(G) графа G — это минимальное число цветов, необходимых для гармонической раскраски графа G.

Гармоническая раскраска 7-дерева с тремя уровнями с использованием 12 цветов. Гармоническое хроматическое число этого графа равно 12, поскольку он имеет 57 рёбер число пар цветов равно ncolor*(ncolor-1)/2 >= 57 если только ncolor>=12. Однако (3/2)*(7+1)=12 (смотрите формулу Митчема (Mitchem).

Любой граф обладает гармонической раскраской, поскольку достаточно раскрасить каждую вершину в свой цвет. Таким образом, χ_H(G) ≤ |V(G)|. Ясно, что существуют графы G с χ_H(G) > χ(G) (где χ — хроматическое число). Примером может служить путь длины 2, вершины которого можно раскрасить двумя цветами, но нет гармонической раскраски с 2 цветами.

Некоторые свойства χ_H(G):

1. χ_H(T_k,3) = ⌈(3/2)(k+1)⌉, где T_k,3 — это полное k-арное дерево с 3 уровнями. (Mitchem 1989)

Гармоническая раскраска была впервые предложена Харари и Плантхолт (Harary, Plantholt, 1982). Мало что известно об этом типе раскраски.

См. также

• Полная раскраска
• Гармоническая разметка

Литература

• O. Frank, F. Harary, M. Plantholt. The line-distinguishing chromatic number of a graph // Ars Combin. — 1982. — Т. 14. — С. 241–252.
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
• J. Mitchem. On the harmonious chromatic number of a graph // Discrete Math.. — 1989. — Т. 74. — С. 151–157. — doi:10.1016/0012-365X(89)90207-0.

Ссылки

• A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards