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