# Revision history [back]

### How to determine if two colorings of a graph are the same?

A coloring of a graph $G$ with vertex set $V$ is the partitioning of $V$ into so called color classes in such a way that no two vertices of the same class are adjacent. A $k$-coloring contains exactly $k$ color classes.

We shall think of a $k$-coloring of $G$ as a map $\psi: V \rightarrow{1,2, \ldots, k}$ such that $\psi^{-1}(i), i=1,2, \ldots, k$, are the color classes of $G$. Naturally two maps, $\psi_1$ and $\psi_2$, represent the same $k$-coloring if and only if $\psi_1=\psi_2 \circ \pi$ for some permutation $\pi$ of ${1,2, \ldots, k}$. (See details in B. Bollobás Uniquely colorable graphs[J]. Journal of Combinatorial Theory, Series B, 1978, 25: 54-61.)

My goal is: given a graph with two $k$-colorings, I want to determine if they are same. I am unsure which function to use. I also want to determine how many different colorings of a graph in this sense.

For example,

from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
for C in all_graph_colorings(G, 3):
print(C)

{0: ['a'], 1: ['b', 'd'], 2: ['c']}
{0: ['a'], 1: ['c'], 2: ['b', 'd']}
{0: ['b', 'd'], 1: ['a'], 2: ['c']}
{0: ['c'], 1: ['a'], 2: ['b', 'd']}
{0: ['b', 'd'], 1: ['c'], 2: ['a']}
{0: ['c'], 1: ['b', 'd'], 2: ['a']}


We obtained six $3$-colorings, and are they the same by definition of same $k$-coloring?

After that, we may obtain all uniquely colorable simple graphs up to 10 vertices. See https://oeis.org/A369223 corresponding to their counts.

Additional information: The chromatic number of $G$, denoted by $\chi(G)$, is the minimal $k$ for which $G$ has a $k$-coloring. A graph with exactly one $k$-coloring is called uniquely $k$-colorable. It is obvious that if $G$ is uniquely $k$-colorable then $\chi(G)=k$ or $n$, so we shall say simply that $G$ is uniquely colorable if it is uniquely $\chi(G)$ colorable.

### How to determine if two colorings of a graph are the same?

A coloring of a graph $G$ with vertex set $V$ is the partitioning of $V$ into so called color classes in such a way that no two vertices of the same class are adjacent. A $k$-coloring contains exactly $k$ color classes.

We shall think of a $k$-coloring of $G$ as a map $\psi: V \rightarrow{1,2, \ldots, k}$ such that $\psi^{-1}(i), i=1,2, \ldots, k$, are the color classes of $G$. Naturally two maps, $\psi_1$ and $\psi_2$, represent the same $k$-coloring if and only if $\psi_1=\psi_2 \circ \pi$ for some permutation $\pi$ of ${1,2, \ldots, k}$. (See details in B. Bollobás Uniquely colorable graphs[J]. Journal of Combinatorial Theory, Series B, 1978, 25: 54-61.)

My goal is: given a graph with two $k$-colorings, I want to determine if they are same. I am unsure which function to use. I also want to determine how many different colorings of a graph in this sense.

For example,

from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
for C in all_graph_colorings(G, 3):
print(C)

{0: ['a'], 1: ['b', 'd'], 2: ['c']}
{0: ['a'], 1: ['c'], 2: ['b', 'd']}
{0: ['b', 'd'], 1: ['a'], 2: ['c']}
{0: ['c'], 1: ['a'], 2: ['b', 'd']}
{0: ['b', 'd'], 1: ['c'], 2: ['a']}
{0: ['c'], 1: ['b', 'd'], 2: ['a']}


We obtained six $3$-colorings, and are they the same by definition of same $k$-coloring?

After that, we may I would like to obtain all uniquely colorable simple graphs up to 10 vertices. See https://oeis.org/A369223 corresponding to their counts.

Additional information: The chromatic number of $G$, denoted by $\chi(G)$, is the minimal $k$ for which $G$ has a $k$-coloring. A graph with exactly one $k$-coloring is called uniquely $k$-colorable. It is obvious that if $G$ is uniquely $k$-colorable then $\chi(G)=k$ or $n$, so we shall say simply that $G$ is uniquely colorable if it is uniquely $\chi(G)$ colorable.

### How to determine if two colorings of a graph are the same?

A coloring of a graph $G$ with vertex set $V$ is the partitioning of $V$ into so called color classes in such a way that no two vertices of the same class are adjacent. A $k$-coloring contains exactly $k$ color classes.

We shall think of a $k$-coloring of $G$ as a map $\psi: V \rightarrow{1,2, \ldots, k}$ such that $\psi^{-1}(i), i=1,2, \ldots, k$, are the color classes of $G$. Naturally two maps, $\psi_1$ and $\psi_2$, represent the same $k$-coloring if and only if $\psi_1=\psi_2 \circ \pi$ for some permutation $\pi$ of ${1,2, \ldots, k}$. (See details in B. Bollobás Uniquely colorable graphs[J]. Journal of Combinatorial Theory, Series B, 1978, 25: 54-61.)

My goal is: given a graph with two $k$-colorings, I want to determine if they are same. I am unsure which function to use. I also want to determine how many different colorings $k$-colorings of a graph in this sense.

For example,

from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
for C in all_graph_colorings(G, 3):
print(C)

{0: ['a'], 1: ['b', 'd'], 2: ['c']}
{0: ['a'], 1: ['c'], 2: ['b', 'd']}
{0: ['b', 'd'], 1: ['a'], 2: ['c']}
{0: ['c'], 1: ['a'], 2: ['b', 'd']}
{0: ['b', 'd'], 1: ['c'], 2: ['a']}
{0: ['c'], 1: ['b', 'd'], 2: ['a']}


We obtained six $3$-colorings, and are they the same by definition of same $k$-coloring?

After that, I would like to obtain all uniquely colorable simple graphs up to 10 vertices. See https://oeis.org/A369223 corresponding to their counts.

Additional information: The chromatic number of $G$, denoted by $\chi(G)$, is the minimal $k$ for which $G$ has a $k$-coloring. A graph with exactly one $k$-coloring is called uniquely $k$-colorable. It is obvious that if $G$ is uniquely $k$-colorable then $\chi(G)=k$ or $n$, so we shall say simply that $G$ is uniquely colorable if it is uniquely $\chi(G)$ colorable.