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

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

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

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

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

1. ${\displaystyle \chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil }$, де ${\displaystyle T_{k,3}}$ — це повне ${\displaystyle 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. .
• J. Mitchem. On the harmonious chromatic number of a graph // Discrete Math.. — 1989. — Т. 74. — С. 151–157. — DOI:10.1016/0012-365X(89)90207-0.

Посилання

• від Кіта Едвардса (Keith Edwards)