L (h, k) -barvení - L(h, k)-coloring

v teorie grafů, a L (h, k)-Značení, L (h, k)-zbarvení nebo někdy L (p, q)-zbarvení je (správné) zbarvení vrcholů ve kterém každá dvojice sousedních vrcholů má čísla barev, která se liší alespoň o h, a všechny uzly spojené cestou 2 délky mají své barvy minimálně odlišné k.^[1] Parametry, h a k se rozumí nezáporná celá čísla.

Problém pocházel z problému s přiřazením kanálu v rádiových sítích. The rozpětí L (h, k) značení, ρ_{h, k}(G) je rozdíl mezi největší a nejmenší přiřazenou frekvencí. Cílem L (h, k) problémem s označováním je obvykle najít označení s minimálním rozpětím.^[2] Pro daný graf je minimální rozpětí všech možných funkcí označování λ_{h, k}-počet G, označeno λ_{h, k}(G).

Když h= 1 a k= 0, je to obvyklé (správné) zbarvení vrcholů.

Existuje velké množství článků týkajících se L (h, k) - označení, s různými h a k parametry a různé třídy grafů.

V některých variantách je cílem minimalizovat počet použitých barev ( objednat).

Viz také

• L (2,1) -barvení

Reference