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

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$$.

• Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices. – Mike Jan 12 at 19:19

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