Harmonické zbarvení - Harmonious coloring

Harmonické zbarvení kompletního 7letého stromu se 3 úrovněmi pomocí 12 barev. Harmonické chromatické číslo tohoto grafu je 12. Jakýkoli menší počet barev způsobí, že se barevný pár objeví na více než jednom páru sousedních vrcholů. Navíc podle Mitchemova vzorce χ_H(T._7,3) = ⌈(3/2)(7+1)⌉ = 12.

v teorie grafů, a harmonické zbarvení je (správné) zbarvení vrcholů ve kterém se každá dvojice barev objeví nejvýše na jednom páru sousedních vrcholů. The harmonické chromatické číslo χ_H(G) grafu G je minimální počet barev potřebných pro harmonické vybarvení G.

Každý graf má harmonické zabarvení, protože stačí každému vrcholu přiřadit jinou barvu; tedy χ_H(G) ≤ | V (G) |. Triviálně existují grafy G s χ_H(G)> χ (G) (kde χ je chromatické číslo ); jedním příkladem je jakákoli cesta délky> 2, která může být dvoubarevná, ale nemá harmonické zbarvení se dvěma barvami.

Některé vlastnosti χ_H(G):

${ displaystyle chi _ {H} (T_ {k, 3}) = left lceil { frac {3 (k + 1)} {2}} right rceil}$ , kde T_k,3 je kompletní $k$ -ary strom se 3 úrovněmi. (Mitchem 1989)

Harmonické zbarvení poprvé navrhli Harary a Plantholt (1982). Stále se o něm ví velmi málo.

Viz také

externí odkazy

Bibliografie harmonických barviv a achromatického čísla Keith Edwards

Reference

Frank, O .; Harary, F .; Plantholt, M. (1982). Msgstr "Čárové rozlišovací chromatické číslo grafu". Ars Combin. 14: 241–252.
Jensen, Tommy R .; Toft, Bjarne (1995). Problémy s barvením grafů. New York: Wiley-Interscience. ISBN 0-471-02865-7.
Mitchem, J. (1989). Msgstr "Na harmonickém chromatickém čísle grafu". Diskrétní matematika. 74: 151–157. doi:10.1016 / 0012-365X (89) 90207-0.