Meno:Olívia
Priezvisko:Kunertová
Názov:Circular chromatic index of small snarks
Vedúci:RNDr. Ján Mazák, PhD.
Rok:2017
Blok:INF
Kµúčové slová:snark, circular chromatic index, circular edge colorability
Abstrakt:The circular chromatic index of a graph $G$ is a refinement of a ordinary chromatic index of a graph. The problem of determining circular chromatic index of a graph belongs to class of a NP-complete problems. The circular chromatic index of a graph $G$ is the smallest rational number $r$ such that $G$ is $r$-circular edge colorable. In this work we will focus on determining circular chromatic index of class of graphs -- snarks. We design and implemented methods determining circular edge colorability. Those methods are then used to compute circular chromatic index of a graph from given potential indices. We compare those methods based on theoretical time complexity as well as their running time. Based on the results we choose the most successful one that will be used to determine circular chromatic indices of small snarks.

Súbory diplomovej práce:

kunertova.pdf