Harmonijna kolorystyka

Harmonijna kolorystyka kompletnego 7-arkowego drzewa z 3 poziomami przy użyciu 12 kolorów. Harmonijna liczba chromatyczna tego wykresu wynosi 12. Mniej kolorów spowoduje, że para kolorów pojawi się na więcej niż jednej parze sąsiednich wierzchołków. Ponadto, zgodnie ze wzorem Mitchema,

χ H (T 7,3) = ⌈(3/2)(7+1)⌉ = 12

.

W teorii grafów harmonijne kolorowanie to (właściwe) kolorowanie wierzchołków , w którym każda para kolorów pojawia się co najwyżej na jednej parze sąsiednich wierzchołków . Jest to przeciwieństwo pełnego kolorowania , które zamiast tego wymaga, aby każde powiązanie kolorów wystąpiło co najmniej raz. Harmonijna liczba chromatyczna $χ H (G)$ wykresu $G$ to minimalna liczba kolorów potrzebnych do dowolnego harmonijnego $zabarwienia$ G .

Każdy graf ma harmonijną kolorystykę, ponieważ wystarczy przypisać każdemu wierzchołkowi odrębny kolor; zatem $χ H (G) \leq | V(G) |$ . Trywialnie istnieją grafy $G$ z $χ H (G) > χ (G)$ (gdzie $χ$ jest liczbą chromatyczną ); jednym z przykładów jest dowolna ścieżka o długości > 2 , która może być dwukolorowa, ale nie ma harmonijnego zabarwienia z 2 kolorami.

Niektóre własności $χ H (G)$ :

{\ Displaystyle \ chi _ {H} (T_ {k, 3}) = \ lewo \ lceil {\ Frac {3 (k + 1 )}{2}}\prawo\rceil ,}

gdzie $T k,3$ jest kompletnym $k$ -arowym drzewem o 3 poziomach. (Mitchem 1989)

Harmonijne kolorowanie zostało po raz pierwszy zaproponowane przez Harary'ego i Plantholta (1982). Wciąż niewiele o nim wiadomo.

Zobacz też

Linki zewnętrzne

Bibliografia harmonijnych kolorów i liczb achromatycznych autorstwa Keitha Edwardsa

Frank, O.; Harary, F.; Plantholt, M. (1982). „Wyróżniająca linie liczba chromatyczna wykresu”. Ars Combin . 14 : 241–252.
Jensen, Tommy R.; Toft, Bjarne (1995). Problemy z kolorowaniem wykresów . Nowy Jork: Wiley-Interscience. ISBN 0-471-02865-7 .
Mitchem, J. (1989). „O harmonijnej liczbie chromatycznej wykresu” . Matematyka dyskretna . 74 : 151–157. doi : 10.1016/0012-365X(89)90207-0 .