# Exact algorithm for edge coloring

Wikipedia lists several exact algorithms for graph vertex coloring.

Are there any exact algorithms that are designed specifically for graph edge coloring?

edit:

Just came across my mind, i think it should be ok (pure bruteforce). I didnt try to implement this yet. Please comment if you see something wrong. Just to say again - algorithm should check whether graph is edge colorable with d or d+1 colors where d is max degree of all vertices in given simple graph, and to find one coloring...

colorEdge(edge, color, extra) {
if (edge colored) return;  //if already colored, return
if (can be colored in color) color it; //if color can be applied, apply it
else {
//else, 'd+1'-st color neded, so color it with that color, continue finding
//coloring with d+1 colors
extra = !extra;
color it in color extra;
}

//recursivly try to color adjacent edges with available colors
for each color c' from set of d colors {
for each edge k adjacent to current {
colorE(k, c', extra)
}
}
}

//main
bool extra = false;
for each color b from set of d colors {
colorEdge(some starting edge, b, extra)
if (!extra) break;
}

• You're looking for efficient exact algorithms for graph coloring: you should take a look at David Eppstein's paper from WADS 2001: arxiv.org/abs/cs.DS/0011009 May 25, 2011 at 20:38
• thanks for fast reply.. i have to find chromatic index (number of minimal colors for edge coloring). in this paper is described finding of chromatic number. i could translate given graph G to line graph H = L(G) and than find chromatic number, but, i think that is a bit overkill because i dont need very (time) efficient algorithm.. May 25, 2011 at 20:46
• ah ok. I was confused. May 25, 2011 at 21:47
• @Goran: I don't think it is good idea to give an algorithm and ask people to verify it. However, a general reference request regarding the existence of edge colouring algorithms should be ok (assuming it is not trivial to google). May 26, 2011 at 0:06
• @Goran, there are an SE site for code review, I think it would be better to post your code there. If you want to describe an algorithm here, it would be better to explain the main ideas behind it in English or pseudo-code. Btw, please read the FAQ if you have not. Thanks. May 26, 2011 at 4:33

You can edge color faster than applying the fastest vertex coloring algorithm to the line graph: see http://arxiv.org/abs/1007.1161 for one such algorithm. What interests me is why can't we find something that is much faster...

You main gain significant time by first computing the fractional chromatic index, which would tell quickly if your graph is class 2. Then Vizing's algorithm would probably do.

In Sage -- even though that's probably not the best solution -- we solve it by LP. If you guys have anything that could help us to solve edge coloring, please please tell me :-)

http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.edge_coloring

The function computing the Fractional Chromatic Index will be available in the next release.

• Are you formulating the LP in an intelligent way? Because as I'm sure you know, if you formulate the LP too naively, it will have exponential size. May 26, 2011 at 18:54
• You mean the fractional chromatic index ? I guess I'm doing it the stupid way, by adding the most interesting matching to the LP at each step :-) After having worked hard to have constraint generation available, it worked on the graphs I was interested in so I was satisfied. Would you know how to improve it ? I'm definitely interested in learning how :-) May 30, 2011 at 9:58
• Oh, perhaps I didn't get what you meant : of course I'm not enumerating all the matchings and writing the LP afterwards. I'm adding matchings to the LP on the fly, so that it should only contain "useful ones" but of course this can mean adding a lot... But then again if you know of any way to improve it, I'd be glad to know :-) May 30, 2011 at 10:20
• No, I was just hoping that you did not take the absolutely naive approach of enumerating all matchings! Jun 13, 2011 at 12:19
• @NathannCohen : could you please explain how the fractional chromatic index helps to figure out if a graph is class 1 or 2? Or point to some literature about this topic? Aug 29, 2015 at 6:49

How about creating the line graph and feeding this to the node-coloring algorithm? Each node in the line graph is defined to correspond to an edge in the original graph, and these "nodes" are joined if the correspond edges in the original graph are adjacent.

I don't know about the speed of this. Perhaps a specialized edge-coloring algorithm would be faster.