COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 5 years ago

#370 new enhancement

Edge coloring algorithms

Reported by: Ben Strasser Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc: mail@…
Revision id:



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

Attachments (1) (3.4 KB) - added by Alpar Juttner 8 years ago.

Download all attachments as: .zip

Change History (2)

Changed 8 years ago by Alpar Juttner

Attachment: added

comment:1 Changed 5 years ago by Balazs Dezso

Milestone: LEMON 1.3 releaseLEMON 1.4 release
Note: See TracTickets for help on using tickets.