| Abstrakt: | A r-circular edge coloring of a graph G = (V, E) is a mapping c : E -> [0, r), where
for any two adjacent vertices e1 and e2, 1 <= |c(e1) - c(e2)| <= r-1 and the circular
chromatic index is the infimum over all r, such that G has a r-circular edge coloring.
A circular r-flow is an asigning of an orientation and a flow function Phi: E -> [1, r - 1]
to the graph, where the flow value of outgoing edges must be equal to the flow value of
incoming edges for every vertex of the graph. There exists a duality between colorings
and nowhere zero flows. This duality however, only exists on a plane. The concept
of circular coloring is equivalent to r-tensions, that were defined by DeVos et al. The
concept of tensions is dual to flows, in spaces other then a plane with added conditions
to ensure the duality outside of a plane. For more effective encoding of conditions of
a flow as a mixed linear program we will be using balanced valuations. We make use
of the circular coloring r-tension duality to construct an algorithm that computes the
circular chromatic index of a graph. We then compare the runtime of this algorithm
to a trivial algorithm for computing circular chromatic index that uses mixed linear
programming.
|
|---|