# Why does all_graph_colorings not generate all possible colorings?

I use all_graph_colorings to generate all possible colorings of a graph $G$ as follows:

sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: G = Graph({0: [1], 1: [2], 2: [3, 5], 3: [4, 6]})
sage: D = {'#ff0000': [0, 4, 5], '#0000ff': [1, 3], '#00ff00': [6, 2]}
sage: print(D in all_graph_colorings(G, 3, hex_colors=True))
False


Is there something I did wrong? Obviously, $D$ must be a $3$-coloring of vertices of $G$, right?

edit retag close merge delete

Sort by ยป oldest newest most voted

The reason is simple.

A graph coloring is a dictionary whose keys are colours and values are lists of vertices of that colour.

The thing is, each list of vertices is sorted.

sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: G = Graph({0: [1], 1: [2], 2: [3, 5], 3: [4, 6]})
sage: C = list(all_graph_colorings(G, 3, hex_colors=True))


Your example has [6, 2] as the last list:

sage: D = {'#ff0000': [0, 4, 5], '#0000ff': [1, 3], '#00ff00': [6, 2]}
sage: D in C
False


Using [2, 6] instead:

sage: D = {'#ff0000': [0, 4, 5], '#0000ff': [1, 3], '#00ff00': [2, 6]}
sage: D in C
True

more

## Stats

Seen: 166 times

Last updated: Jul 09 '21