Přejít k obsahu


Vrcholová barvení distančního typu v grafech

Citace:
HOLUB, P. Vrcholová barvení distančního typu v grafech. Plzeň, 2017.
Druh: PŘEDNÁŠKA, POSTER
Jazyk publikace: cze
Rok vydání: 2017
Autoři: Doc. RNDr. Přemysl Holub Ph.D. ,
Abstrakt CZ: Vrcholové barvení grafů (tedy přiřazení číselných hodnot vrcholům grafu) je jednou z velmi intenzivně zkoumaných oblastí teorie grafů a má široké uplatnění v reálném světě, například při barvení map, plánování procesů a rozvrhování akcí, nebo v problému přiřazování frekvencí. Cílem této přednášky se seznámit posluchače s vrcholovými barveními distančního typu, která jsou motivována problémem přiřazování frekvencí, především tzv. pakovacím a S-pakovacím barvením, a distančním barvením. Při tomto typu vrcholových barvení je snahou minimalizovat počet použitých barev - stanovit tzv. chromatické číslo pro daný typ barvení (například pakovací chromatické číslo). Nalezení těchto chromatických čísel pro uvedené typy barvení je velmi obtížná úloha již jen pro velmi specifické třídy grafů a algoritmicky se obecně jedná o NP-úplné a NP-těžké problémy. V této přednášce se budeme zabývat některými třídami grafů, pro něž lze stanovit přesné hodnoty těchto chromatických parametrů, nebo alespoň nalézt horní a dolní meze pro tyto parametry. Rovněž ukážeme některé nekonečné třídy grafů, pro něž jsou tyto parametry libovolně velké, tj. není možné grafy z dané třídy obarvit konečným počtem barev.
Klíčová slova

Zpět

Patička