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 NPcomplete 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.

