| Meno: | Olívia
|
|---|
| Priezvisko: | Kunertová
|
|---|
| Názov: | Circular chromatic index of small snarks
|
|---|
| Vedúci: | RNDr. Ján Mazák, PhD.
|
|---|
| Rok: | 2017
|
|---|
| 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.
|
|---|