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

CC BY-SA 3.0
2011-05-26T06:42:03.147Z
2011-05-26T06:42:03.147Z
Andreas Björklund
<p>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.</p>

<p>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 :-)</p>

<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.edge_coloring" rel="nofollow">http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.edge_coloring</a></p>

<p>The function computing the Fractional Chromatic Index will be available in the next release.</p>

CC BY-SA 3.0
2011-05-26T18:54:51.783Z
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.
Andrew D. King
CC BY-SA 3.0
2011-05-30T09:58:11.307Z
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 :-)
Nathann Cohen
CC BY-SA 3.0
2011-05-30T10:20:57.130Z
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 :-)
Nathann Cohen
CC BY-SA 3.0
2011-06-13T12:19:41.800Z
No, I was just hoping that you did not take the absolutely naive approach of enumerating all matchings!
Andrew D. King
CC BY-SA 3.0
2015-08-29T06:49:39.080Z
@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?
jhegedus
CC BY-SA 3.0
2011-05-26T07:22:05.680Z
2011-05-26T07:22:05.680Z
Nathann Cohen
<p>How about creating the <a href="http://en.wikipedia.org/wiki/Line_graph" rel="nofollow">line graph</a> 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.</p>

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

<p>Perhaps you already considered this?</p>

CC BY-SA 3.0
2011-05-25T23:22:38.397Z
yes yes, i was thinking about this (u can see my comment to my post).. look at the updated post!
Goran F
CC BY-SA 3.0
2011-05-25T23:14:58.130Z
2011-05-25T23:14:58.130Z
Aaron McDaid
<p>Wikipedia lists <a href="http://en.wikipedia.org/wiki/Graph_coloring#Exact_algorithms" rel="nofollow">several exact algorithms for graph vertex coloring</a>.</p>

<p>Are there any exact algorithms that are designed specifically for graph <em>edge</em> coloring?</p>

<p>edit:</p>

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

<pre><code>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;
}
</code></pre>

CC BY-SA 3.0
2011-05-25T20:38:04.713Z
You're looking for efficient exact algorithms for graph coloring: you should take a look at David Eppstein's paper from WADS 2001: http://arxiv.org/abs/cs.DS/0011009
Suresh Venkat
CC BY-SA 3.0
2011-05-25T20:46:10.693Z
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..
Goran F
CC BY-SA 3.0
2011-05-25T21:47:54.983Z
ah ok. I was confused.
Suresh Venkat
CC BY-SA 3.0
2011-05-26T00:06:42.350Z
@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).
Jukka Suomela
CC BY-SA 3.0
2011-05-26T00:18:08.493Z
sorry if i broke some rule, i dont have any wrong intentions :). It came across my mind and i wanted to share it because i didnt find anything similiar yet, although its simple recursion (as i see on google and some other forums, this problem is rarely covered). I decided to put it here, if anyone need it.. Just to mention again, im not asking anyone to solve anything for me, but hints or ideas are welcome :)
Goran F
CC BY-SA 3.0
2011-05-26T04:33:00.097Z
@Goran, there are an SE site for [code review](http://codereview.stackexchange.com/), 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.
Kaveh
<ds.algorithms><graph-theory><graph-algorithms>
Exact algorithm for edge coloring
Goran F
# Exact algorithm for edge coloring

(Asked by: username_0 on 2011-05-25)

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;
}

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: You're looking for efficient exact algorithms for graph coloring: you should take a look at David Eppstein's paper from WADS 2001: http://arxiv.org/abs/cs.DS/0011009  
> **username_0**: 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..  
> **username_1**: ah ok. I was confused.  
> **username_2**: @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).  
> **username_0**: sorry if i broke some rule, i dont have any wrong intentions :). It came across my mind and i wanted to share it because i didnt find anything similiar yet, although its simple recursion (as i see on google and some other forums, this problem is rarely covered). I decided to put it here, if anyone need it.. Just to mention again, im not asking anyone to solve anything for me, but hints or ideas are welcome :)  
> **username_3**: @Goran, there are an SE site for [code review](http://codereview.stackexchange.com/), 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.  

---

## 3 answers

### Answer by username_4 on 2011-05-26. Score: 10

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


---

### Answer by username_5 on 2011-05-26. Score: 4

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.

> **Comments:**
> **username_6**: 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.  
> **username_5**: 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 :-)  
> **username_5**: 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 :-)  
> **username_6**: No, I was just hoping that you did not take the absolutely naive approach of enumerating all matchings!  
> **username_7**: @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?  

---

### Answer by username_8 on 2011-05-25. Score: 2

How about creating the [line graph](http://en.wikipedia.org/wiki/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?

> **Comments:**
> **username_0**: yes yes, i was thinking about this (u can see my comment to my post).. look at the updated post!  

---

