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

розфарбування вершин графа, за якого будь-яка пара кольорів з'являється на суміжних вершинах не більше одного разу

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

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

Будь-який граф має гармонійне розфарбування, оскільки, щоб його отримати, достатньо розфарбувати кожну вершину в свій колір. Таким чином, . Ясно, що існують графи з (де χ — хроматичне число). Прикладом є шлях довжини 2, вершини якого можна розфарбувати двома кольорами, але немає гармонійного розфарбування з 2 кольорами.

Деякі властивості :

  1. , де  — це повне -арне дерево з 3 рівнями. (Mitchem, 1989)

Гармонійне розфарбування вперше запропонували Гарарі і Плантголт (Harary, Plantholt, 1982). Наразі про цей тип розфарбування відомо мало.

Див. також

ред.

Література

ред.

Посилання

ред.