ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 09 Jul 2021 15:53:36 +0200Why does `all_graph_colorings` not generate all possible colorings?https://ask.sagemath.org/question/57933/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?
Fri, 09 Jul 2021 05:27:44 +0200https://ask.sagemath.org/question/57933/why-does-all_graph_colorings-not-generate-all-possible-colorings/Answer by slelievre for <p>I use <code>all_graph_colorings</code> to generate all possible colorings of a graph $G$ as follows:</p>
<pre><code>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
</code></pre>
<p>Is there something I did wrong? Obviously, $D$ must be a $3$-coloring of vertices of $G$, right?</p>
https://ask.sagemath.org/question/57933/why-does-all_graph_colorings-not-generate-all-possible-colorings/?answer=57937#post-id-57937The 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
Fri, 09 Jul 2021 15:53:36 +0200https://ask.sagemath.org/question/57933/why-does-all_graph_colorings-not-generate-all-possible-colorings/?answer=57937#post-id-57937