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})=\lceil \frac{3(k+1)}{2}\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

• Sablon:Fordítás

Jegyzetek

• Sablon:Cite journal
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. Sablon:ISBN.
• Sablon:Cite journal