Edge coloring algorithms

[Ben Strasser]

Hello,

for a project I am working on I had to implement a couple of edge coloring algorithms. If there is any interest I could LEMON-ify them.

A valid edge coloring is a coloring of the edges so that each node has no two incident edges colored in the same way.

What is implemented is:

• An edge map to store valid colorings and that supports the queries

needed by the algorithms in a fast way.

• An algorithm that colors bipartite graphs using at most as many colors

as the maximum node degree.

• Vizing's algorithm to color general simple graphs using at most as

many colors as the maximum node degree + 1.

• Test cases

Both algorithms are in O(m*n)

For general simple graphs it is not always possible to color them using only maximum node degree. An example is K_3. Determining if this is possible is NP-hard so Vizing's algorithm seems to be the best you can get within polynomial time.

I've attached my code.

Best regards, Ben Strasser