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

Гармонійне розфарбування 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)\leq |V(G)|$. Ясно, що існують графи $G$ з $\chi _{H}(G)>\chi (G)$ (де χ — хроматичне число). Прикладом є шлях довжини 2, вершини якого можна розфарбувати двома кольорами, але немає гармонійного розфарбування з 2 кольорами.

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

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