| Abstrakt: | L(2,1)-farbenie je vzdialenosťou podmienené farbenie, ktoré priradzuje vrcholom prirodzené čísla s nulou. Susedné vrcholy musia mať čísla, ktoré sa líšia aspoň o dva a vrcholy, ktoré sú vo vzdialenosti dva, musia mať rôzne čísla. Chceme vedieť, aké je najmenšie číslo k, že existuje L(2,1)-farbenie grafu G, ktoré nepoužíva čísla väčšie ako k. Toto číslo potom označujeme lambda(G). Nájsť lambda(G) je vo všeobecnosti veľmi ťažké. Dokonca otestovať či lambda(G) <= k je NP-úplný problém už pre sériovo-paralelné grafy. Existuje len málo tried grafov, kde je tento problém polynomiálne riešiteľný. Triedy, ktoré patria do tejto kategórie sú stromy a grafy s konštantným počtom cyklov. My sme tento poznatok rozšírili o triedu cyklových stromov (kaktusy s vrcholovo disjunktnými kružnicami). Ďalej sme určili tesné ohraničenia lambda(G) vzhľadom na maximálny stupeň grafu. Dokázali sme, že pre každý kaktus G s maximálnym stupňom Delta platí: Delta+1 <= lambda(G) <= Delta+3. Ak navyše Delta >= 5, tak platí: Delta+1 <= lambda(G) <= Delta+2.
|
|---|