2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mike Jan 12 at 19:19
3
+100
$\begingroup$

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())

graph coloring

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.