A gráfelméletben a harmonikus színezés egy (megfelelő) csúcsszínezés , amelynél bármely színpár legfeljebb egyszer jelenik meg a szomszédos csúcsokon. A G gráf χ H ( G ) harmonikus kromatikus száma a G gráf harmonikus színezéséhez szükséges minimális színek száma .
Minden gráfnak van harmonikus színezése, mivel elegendő minden csúcsot más színnel színezni. Így χ H ( G ) ≤ |V(G)|. Nyilvánvaló, hogy vannak G gráfok , amelyeknél χ H ( G ) > χ( G ) (ahol χ egy kromatikus szám ). Példa erre egy 2 hosszúságú út, amelynek csúcsai két színnel színezhetők, de nincs harmonikus színezés 2 színnel.
A χ H ( G ) néhány tulajdonsága:
A harmonikus színezést először Harary és Plantholt javasolta (1982). Keveset tudunk az ilyen típusú színezésről.