Harmonikus színezés

Három szintű, 7-szeresen elágazó fa 12 színnel történő harmonikus színezése. A fa harmonikus kromatikus száma 12, mivel kevesebb színt használva lenne olyan színpár, ami egynél több szomszédos csúcspáron jelentkezne. Továbbá, a Mitchem-képlet alapján χ_H(T_7,3) = ⌈(3/2)(7+1)⌉ = 12.

A matematika, azon belül a gráfelmélet területén egy harmonikus színezés olyan (jó) csúcsszínezés, melyben minden színpáros legfeljebb egy szomszédos csúcspáron jelenik meg. A G gráf harmonikus kromatikus száma, χ_H(G) a minimális számú szín, ami szükséges G harmonikus színezéséhez.

Minden gráfnak van harmonikus színezése, hiszen minden csúcs különböző színre színezése megfelel a feltételeknek; ezért χ_H(G) ≤ |V(G)|. Triviális, hogy léteznek olyan G gráfok, melyekre χ_H(G) > χ(G) (ahol χ a kromatikus szám); példa erre az összes, 2-nél nagyobb hosszúságú út, melyek 2-színezhetők, de nincsen harmonikus 2-színezésük.

A χ_H(G) néhány tulajdonsága:

1. $\chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil$, ahol T_k,3 a 3 szintű teljes k-áris fa. (Mitchem 1989)

A harmonikus színezést elsőként Harary and Plantholt (1982) vetették fel. Még mindig keveset tudni vele kapcsolatban.

Kapcsolódó szócikkek

• Teljes színezés
• Harmonikus címkézés

További információk

• A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards

Fordítás

• Ez a szócikk részben vagy egészben a Harmonious coloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (1982) „The line-distinguishing chromatic number of a graph”. Ars Combin 14, 241–252. o. 
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
• (1989) „On the harmonious chromatic number of a graph”. Discrete Math. 74, 151–157. o. DOI:10.1016/0012-365X(89)90207-0.