Colpack appears to have OpenMP support but not MPI. Would it really be enough of an improvement on what we have now to need adding an actual interface and externalpackage? Stefano, what's your experience here?
I gave Colpack a try for its different coloring options. No efficiency reasons: the graph I had to color was a face-centered adjacency graph of subdomains connectivity, so very few vertices and edges. With very regular domains (cubes) in 3D and such a graph, Colpack returns a coloring with 18-20 colors which is almost the optimal number of colors (18).
Instead, what about Boost? Have you ever tried it?
The group who publishes the most on this stuff put their distributed memory implementations of distance 1 and 2 matrix coloring into Zoltan. I've updated the externalpackage to the latest version in a branch, and am now wrapping it.
I've got my own implementations, but they're probably not as well tested yet.
An update; the Zoltan coloring algorithms take the passed-in communicator for some sort of wild ride that through some nasty set of duplications and reduplications breaks our reference counting. I've tried to trace it and fix it and it's pretty deep in their code way away from the coloring algorithms where it happens and doesn't happen for a good reason.
Some good news, however, is that I've been able to test -mat_coloring_type greedy and (the slower but general-distance) -mat_coloring_type jp for distance 1 and distance 2 coloring. These are ready for testing and open for feature or interface suggestions if need be.