Гармоничный колорит

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

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

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

${\displaystyle \chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil ,}$

где T _{k ,3} — полное k -арное дерево с 3 уровнями. (Mitchem 1989)

Гармоничная окраска была впервые предложена Харари и Плантхолтом (1982). До сих пор о ней известно очень мало.

• Полная окраска
• Гармоничная маркировка

• Библиография гармонических цветов и ахроматических чисел Кейта Эдвардса

• Франк, О.; Харари, Ф.; Плантхолт, М. (1982). «Хроматическое число графа, различающее линии». Ars Combin . 14 : 241–252.
• Дженсен, Томми Р.; Тофт, Бьярне (1995). Задачи раскраски графов . Нью-Йорк: Wiley-Interscience. ISBN 0-471-02865-7 . 
• Митчем, Дж. (1989). «О гармоническом хроматическом числе графа». Discrete Math . 74 (1–2): 151–157. doi : 10.1016/0012-365X(89)90207-0 .