Гармонійне розфарбування

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

У теорії графів гармоні́йне розфарбува́ння — це (правильне) розфарбування вершин, за якого будь-яка пара кольорів з'являється на суміжних вершинах не більше одного разу. Гармоні́йне хромати́чне число́ ${\chi }_H(G)$ графа $G$ — це найменше число кольорів, необхідних для гармонійного розфарбування графа $G$.

Будь-який граф має гармонійне розфарбування, оскільки, щоб його отримати, достатньо розфарбувати кожну вершину в свій колір. Таким чином, ${\chi }_H(G)\le |V(G)|$. Ясно, що існують графи $G$ з ${\chi }_H(G)>\chi (G)$ (де χ — хроматичне число). Прикладом є шлях довжини 2, вершини якого можна розфарбувати двома кольорами, але немає гармонійного розфарбування з 2 кольорами.

Деякі властивості ${\chi }_H(G)$:

1. ${\chi }_H(T_{k,3})=\lceil \frac{3(k+1)}{2}\rceil$, де $T_{k,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 від Кіта Едвардса (Keith Edwards)