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

В теории графов гармоничная раскраска — это (правильная) раскраска вершин , при которой каждая пара цветов появляется не более чем на одной паре соседних вершин . Это противоположность полной раскраски , которая вместо этого требует, чтобы каждая пара цветов встречалась хотя бы один раз. Гармоничное хроматическое число $χH раскраски (G)$ графа G $G.$ это минимальное количество цветов, необходимое для любой гармоничной $графа$ —

Каждый граф имеет гармоничную раскраску, поскольку достаточно присвоить каждой вершине отдельный цвет; таким образом, $χ ЧАС (G) \leq | В(г) |$ . Тривиально существуют графы $G$ такие, что $(χH G) > χ(G)$ (где $χ$ — хроматическое число ); Одним из примеров является любой путь длиной > 2 , который может быть двухцветным, но не имеет гармоничной раскраски двумя цветами.

Некоторые свойства $χ H (G)$ :

\chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil ,

где $T k,3$ — полное $k$ -арное дерево с 3 уровнями. (Митчем, 1989)

Гармоничная окраска была впервые предложена Харари и Плантхолтом (1982). О нем пока известно очень мало.

См. также

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

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

Ссылки

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