Meno:Barbora
Priezvisko:Candráková
Názov:Cirkulárny chromatický index Szekeresovych snarkov
Vedúci:Mgr. Ján Mazák
Rok:2009
Kľúčové slová:cirkulárny chromatický index, r-farbenie, hranové farbenie, Szekeresov snark
Abstrakt:Jedným zo zjemnení chromatického indexu, ktoré sa nedávno začalo skúmať, je cirkulárny chromatický index. it Cirkulárne hranové farbenie grafu $G$ je zobrazenie $c\colon E(G) \to [0, r)$, kde pre každé dve susedné hrany $e$ a $f$ platí: $1\leq |c(e)-c(f)|\leq r-1$. {\it Cirkulárny chromatický index} je infímum množiny všetkých $r$ takých, že graf $G$ má cirkulárne $r$-hranové-farbenie. Tento invariant je zaujímavý najmä pre snarky, bezmostové kubické grafy s chromatickým indexom štyri. V tejto práci sa budeme zaoberať jednou z nekonečných tried snarkov, konkrétne zovšeobecnenými Szekeresovými snarkami, a určíme presnú hodnotu cirkulárneho chromatického indexu dvoch najmenších snarkov z tejto triedy. Najmenší graf rádu 50 má hodnotu cirkulárneho chromatického indexu $3 + 2/11$. Týmto sme vyriešili otvorený problém, ktorý bol vyslovený Gheblehom v roku 2008. Taktiež určíme netriviálnu hornú a dolnú hranicu cirkulárneho chromatického indexu zovšeobecnených Szekeresových snarkov.

Súbory bakalárskej práce:

bakalarka.pdf