4
$\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;
}
Improve this question
$\endgroup$
6
  • 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, 2011 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, 2011 at 20:46
  • $\begingroup$ ah ok. I was confused. $\endgroup$
    – Suresh Venkat
    May 25, 2011 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, 2011 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, 2011 at 4:33

3 Answers 3

Reset to default
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...

Improve this answer
$\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.

Improve this answer
$\endgroup$
5
  • $\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, 2011 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, 2011 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, 2011 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, 2011 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, 2015 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?

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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