3
$\begingroup$

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;
}
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat May 25 '11 at 20:38
  • $\begingroup$ 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.. $\endgroup$ – Goran F May 25 '11 at 20:46
  • $\begingroup$ ah ok. I was confused. $\endgroup$ – Suresh Venkat May 25 '11 at 21:47
  • 4
    $\begingroup$ @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). $\endgroup$ – Jukka Suomela May 26 '11 at 0:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh May 26 '11 at 4:33
10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andrew D. King May 26 '11 at 18:54
  • $\begingroup$ 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 :-) $\endgroup$ – Nathann Cohen May 30 '11 at 9:58
  • $\begingroup$ 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 :-) $\endgroup$ – Nathann Cohen May 30 '11 at 10:20
  • $\begingroup$ No, I was just hoping that you did not take the absolutely naive approach of enumerating all matchings! $\endgroup$ – Andrew D. King Jun 13 '11 at 12:19
  • $\begingroup$ @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? $\endgroup$ – jhegedus Aug 29 '15 at 6:49
2
$\begingroup$

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.

Perhaps you already considered this?

$\endgroup$
  • $\begingroup$ yes yes, i was thinking about this (u can see my comment to my post).. look at the updated post! $\endgroup$ – Goran F May 25 '11 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.