Command to compute the number of $5$-colorings of all $(2k, k^2)$-graphs

Question

I would like Sage to compute the number of all $5$-colorings of graphs on $2k$ vertices and $k^2$ edges with clique number 3 for a specified $k \geq 1$.

I know how to ask call nauty and ask sage to generate, for example, all graphs on $2k=8$ and $k^2=16$ vertices with clique number $3$:

g8 = [g for g in graphs.nauty_geng('8 16') if g.clique_number() == 3]

Is there a way to obtain a list of the number of $5$-colorings of all of these graphs? If not, could I at least obtain their chromatic polynomials? Then I could have them evaluated at $5$.

Thank you in advance for your help.

Answer 1

Yes, you can obtain the numbers by number_of_n_colorings:

sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: c8 = [number_of_n_colorings(g,5) for g in g8]; c8
[7740,
11640,
...
7140,
6120]

The result is the same as evaluating the chromatic polynomials at $5$:

sage: [g.chromatic_polynomial()(5) for g in g8] == c8
True

You can also obtain all the colorings by using all_graph_colorings:

sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: colorings = [list(all_graph_colorings(g,5)) for g in g8]

The first coloring of the first graph is as follows:

sage: colorings[0][0]
{0: [0, 1, 2, 3, 4], 1: [5, 6], 2: [7]}

The keys in the dictionary are the colors and the values are the lists of vertices with that color (see the vertex_color_dict argument of all_graph_colorings if you want the output the other way around). Hence colorings[0][0].values() is the partition of the vertex set into colors. We can use this partition to plot the graph with colors:

sage: g8[0].plot(partition=colorings[0][0].values())

Also, the list of all colorings agrees with the list of numbers obtained earlier:

sage: [len(c) for c in colorings] == c8
True