C++ Graph Vertex Coloring Library or Source Code

Question

Is there a C++ (or any other language) library with a portfolio of algorithms for the problem of graph coloring?

There are of course naive greedy vertex coloring algorithms, but I'm interested in more interesting algorithms like:

1. Algorithms mentioned in the "Exact Algorithms" section of the wiki
2. Approximation algorithms that take advantage of special graph properties like the graph being planar or a unit disk graph.
3. Algorithms that find the fractional coloring of a graph.

That last one is of particular importance to me.

What I found so far is the list on this page but none of them have any of the above algorithms. Moreover, the best one is Joe Culberson's Graph Coloring code and that was implemented in late 90's, so is very much outdated in terms of not having a documented API (not that this is important for what this question is about, but I thought I'd mention it).

There's the Koala graph coloring library that has the spirit of what I'm looking for, but if you look at their source code it has not delivered on the promise just yet. It appears to be in very early stages of development.

Other general graph libraries are mentioned in this stackoverflow question. They include:

1. Graphviz
2. Boost Graph Library
3. Lemon
4. igraph
5. OGDF

I should note that I use the Boost Graph Library for a lot of things. In fact, it provides a naive vertex coloring implementation. Joe Culberson's code (mentioned above) does much more.

The following is a list of graph coloring code, I've found (and tested in most cases) but they still mostly fall short in terms of the three algorithm classes above.

1. GraphCol - documentation is not in English, sigh.
2. Planarity - contains a coloring algorithm that guarantees a 5-coloring or better for planar graphs.
3. Graph-Coloring - appears to be a re-implementation of a small number of algorithms already implemented by Joe Culberson (above).

Answer 1

There's some good ones at http://rhydlewis.eu/gcol/. These correspond to a portfolio of algorithms reviewed and tested in my book:

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5. https://link.springer.com/book/10.1007/978-3-030-81054-2

These include greedy, backtracking and metaheuristic approaches. I've included compilation instructions etc. in the above link.

Answer 2

Maybe you can help yourself with the Boost Graph Library.