WikiDer > Гармоничная окраска

Гармоничная раскраска полного 7-ми арного дерева с 3 уровнями с использованием 12 цветов. Гармоничное хроматическое число этого графа равно 12. Любое меньшее количество цветов приведет к появлению пары цветов на более чем одной паре смежных вершин. Более того, по формуле Митчема χ_ЧАС(Т_7,3) = ⌈(3/2)(7+1)⌉ = 12.

В теория графов, а гармоничная окраска это (собственная) раскраска вершин в котором каждая пара цветов появляется не более чем на одной паре смежных вершин. В гармоничное хроматическое число χ_ЧАС(г) графа г минимальное количество цветов, необходимое для гармоничного окрашивания г.

Каждый граф имеет гармоничную раскраску, поскольку достаточно присвоить каждой вершине отдельный цвет; таким образом, χ_ЧАС(г) ≤ | V (г) |, Графы существуют тривиально г с χ_ЧАС(г)> χ (г) (где χ - хроматическое число); один из примеров - любой путь длиной> 2, который может быть двухцветным, но не имеет гармоничной раскраски в два цвета.

Некоторые свойства χ_ЧАС(г):

1. ${ displaystyle chi _ {H} (T_ {k, 3}) = left lceil { frac {3 (k + 1)} {2}} right rceil}$, где T_k,3 это полный k-ари дерево с 3-мя уровнями. (Митчем, 1989)

Гармоничная окраска была впервые предложена Harary and Plantholt (1982), но о ней известно очень мало.

Смотрите также

• Полная окраска
• Гармоничная маркировка

внешние ссылки

• Библиография гармоничных раскрасок и ахроматических чисел Кит Эдвардс

использованная литература

• Франк, O .; Harary, F .; Плантхольт, М. (1982). «Хроматическое число, различающее линии графа». Арс Комбин. 14: 241–252.
• Дженсен, Томми Р .; Тофт, Бьярн (1995). Задачи раскраски графов. Нью-Йорк: Wiley-Interscience. ISBN 0-471-02865-7.
• Митчем, Дж. (1989). «О гармоничном хроматическом числе графа». Дискретная математика. 74: 151–157. Дои:10.1016 / 0012-365X (89) 90207-0.