Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors

Details Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors

2011-04-11

arxiv.org/abs/1104.1852v1

Computer Science

Data Structures and Algorithms

Scientific paper

This paper explores the application of a new algebraic method of color exchanges to the edge coloring of simple graphs. Vizing's theorem states that the edge coloring of a simple graph $G$ requires either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum vertex degree of $G$. Holyer proved that it is {\bf NP}-complete to decide whether $G$ is $\Delta$-edge-colorable even for cubic graphs. By introducing the concept of complex colors, we show that the color-exchange operation follows the same multiplication rules as quaternion. An initially $\Delta$-edge-colored graph $G$ allows variable-colored edges, which can be eliminated by color exchanges in a manner similar to variable eliminations in solving systems of linear equations. The problem is solved if all variables are eliminated and a properly $\Delta$-edge-colored graph is reached. For a randomly generated graph $G$, we prove that our algorithm returns a proper $\Delta$-edge-coloring with a probability of at least 1/2 in $O(\Delta|V||E|^5)$ time if $G$ is $\Delta$-edge-colorable. Otherwise, the algorithm halts in polynomial time and signals the impossibility of a solution, meaning that the chromatic index of $G$ probably equals $\Delta+1$. Animations of the edge-coloring algorithms proposed in this paper are posted at YouTube http://www.youtube.com/watch?v=KMnj4UMYl7k.

Affiliated with

Also associated with

No associations

Rating

Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-58139