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é
Reference
- ^ Chartrand, Gary; Zhang, Ping (2009). "14. Barvení, vzdálenost a nadvláda". Teorie chromatického grafu. CRC Press. 397–438.
- ^ Tiziana, Calamoneri (2006), „Problém značení L (h, k): průzkum a anotovaná bibliografie“, Comput. J., 49 (5): 585–608, doi:10.1093 / comjnl / bxl018