Ask Your Question
1

Why does `all_graph_colorings` not generate all possible colorings?

asked 2021-07-09 05:27:44 +0200

hoanganhduc gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2021-07-09 15:53:36 +0200

slelievre gravatar image

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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-07-09 05:27:44 +0200

Seen: 36 times

Last updated: Jul 09 '21