У теорії графів гармоні́йне розфарбува́ння — це (правильне) розфарбування вершин, за якого будь-яка пара кольорів з'являється на суміжних вершинах не більше одного разу. Гармоні́йне хромати́чне число́ графа — це найменше число кольорів, необхідних для гармонійного розфарбування графа .
Будь-який граф має гармонійне розфарбування, оскільки, щоб його отримати, достатньо розфарбувати кожну вершину в свій колір. Таким чином, . Ясно, що існують графи з (де χ — хроматичне число). Прикладом є шлях довжини 2, вершини якого можна розфарбувати двома кольорами, але немає гармонійного розфарбування з 2 кольорами.
Деякі властивості :
, де — це повне -арне дерево з 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 від Кіта Едвардса (Keith Edwards)