Approximate counting of vertex k-colorings

[fomalhaut-b]

Counting the number of colorings of vertices using k colors, such that every adjacent pair receives different colors is a well-studied problem in theoretical computer science. It is known to be #P-hard (a polynomial time algorithm is unlikely to exist). However, it is possible to approximate in polytime using a sampling algorithm of Jerrum (for the case when k>2*maxdegree).

In networkx, one can compute this value by first computing the chromatic polynomial, and then evaluating that polynomial at k. This is extremely slow, since the algorithm is not polynomial, probably even slower than exponential.

Proposal: add an algorithm in networkx to support jerrum's algorithm. practical experiments on my computer showed that there is a significant speed-up in runtime.

Reference: A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Mark Jerrum, 1994

I am unfamiliar with the process of contributing here, can someone help me out?

[rossbar]

I am unfamiliar with the process of contributing here, can someone help me out?

Probably the best place to start is the contributor guide, which should hopefully get you started working with the codebase.

Proposal: add an algorithm in networkx to support jerrum's algorithm

I'm certainly no expert but at face value this seems like a reasonable addition! Based on the description above, this seems like it would fit best in the networkx.algorithms.approximation package. From a quick glance there doesn't appear to be a module (i.e. .py file) dedicated to coloring, so perhaps creating a networkx/algorithms/approximation/coloring.py would be a good way to organize things for now.