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.Thu, 22 Feb 2024 01:43:22 +0100How to determine if two colorings of a graph are the same?https://ask.sagemath.org/question/76113/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 $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.
[1]: https://i.stack.imgur.com/9z0OO.pngTue, 20 Feb 2024 11:32:41 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/Answer by Max Alekseyev for <p>A <strong>coloring</strong> of a graph $G$ with vertex set $V$ is the partitioning of $V$ into so called <em>color classes</em> in such a way that no two vertices of the same class are adjacent. A <strong>$k$-coloring</strong> contains exactly $k$ color classes. </p>
<p>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 <strong>same $k$-coloring</strong> 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.)</p>
<p><strong>My goal is:</strong> 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 $k$-colorings of a graph in this sense.</p>
<p>For example, </p>
<pre><code>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']}
</code></pre>
<p>We obtained six $3$-colorings, and are they the same by definition of same $k$-coloring? </p>
<p>After that, I would like to obtain all uniquely colorable simple graphs up to 10 vertices. See <a href="https://oeis.org/A369223">https://oeis.org/A369223</a> corresponding to their counts.</p>
<blockquote>
<p>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.</p>
</blockquote>
https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?answer=76122#post-id-76122You can represent colorings as (unordered) set partitions of vertices:
from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
unique_colorings = set( map(SetPartition, all_graph_colorings(G, 3, color_classes=True)) )
for C in unique_colorings:
print(C)
This tells us that there is just one partition:
{{'a'}, {'b', 'd'}, {'c'}}Tue, 20 Feb 2024 18:34:21 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?answer=76122#post-id-76122Comment by licheng for <p>You can represent colorings as (unordered) set partitions of vertices:</p>
<pre><code>from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
unique_colorings = set( map(SetPartition, all_graph_colorings(G, 3, color_classes=True)) )
for C in unique_colorings:
print(C)
</code></pre>
<p>This tells us that there is just one partition:</p>
<pre><code>{{'a'}, {'b', 'd'}, {'c'}}
</code></pre>
https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76157#post-id-76157I know. But it always iterates over all colorings in your code. If G that is not k-coloring, we may quickly test it avoiding all colorings. I want to write a correct code to replace `coloring in enumerate(cl)` in my codesThu, 22 Feb 2024 01:43:22 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76157#post-id-76157Comment by licheng for <p>You can represent colorings as (unordered) set partitions of vertices:</p>
<pre><code>from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
unique_colorings = set( map(SetPartition, all_graph_colorings(G, 3, color_classes=True)) )
for C in unique_colorings:
print(C)
</code></pre>
<p>This tells us that there is just one partition:</p>
<pre><code>{{'a'}, {'b', 'd'}, {'c'}}
</code></pre>
https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76146#post-id-76146Thank you. I try it but not good for me. Would you write a function? My rough idea is to write it like this( the following is just an algorithm, and is not guaranteed to right due to the operator `SetPartition(coloring) in Z`)
def unique_ch(g, k):
if g.chromatic_number()!=k:
return False
flag = True
Z = []
cl = all_graph_colorings(g, k, color_classes=True)
for i, coloring in enumerate(cl): # may wrong
if i == 0:
Z.append(SetPartition(coloring))
else:
if SetPartition(coloring) in Z:
flag = False
break
return flag
Thank you in advance.Wed, 21 Feb 2024 18:52:26 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76146#post-id-76146Comment by Max Alekseyev for <p>You can represent colorings as (unordered) set partitions of vertices:</p>
<pre><code>from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
unique_colorings = set( map(SetPartition, all_graph_colorings(G, 3, color_classes=True)) )
for C in unique_colorings:
print(C)
</code></pre>
<p>This tells us that there is just one partition:</p>
<pre><code>{{'a'}, {'b', 'd'}, {'c'}}
</code></pre>
https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76149#post-id-76149I've already provided code for computing `unique_colorings` - just check `len(unique_colorings) == 1` to make sure that there is one and only coloring.Wed, 21 Feb 2024 21:47:27 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76149#post-id-76149Comment by Max Alekseyev for <p>You can represent colorings as (unordered) set partitions of vertices:</p>
<pre><code>from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
unique_colorings = set( map(SetPartition, all_graph_colorings(G, 3, color_classes=True)) )
for C in unique_colorings:
print(C)
</code></pre>
<p>This tells us that there is just one partition:</p>
<pre><code>{{'a'}, {'b', 'd'}, {'c'}}
</code></pre>
https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76142#post-id-76142Hashable sets are provided by Python's `frozenset` or by Sage's `Set` types. Alternatively, you can create set partitions from lists/tuples - like `SetPartition( [{'a'}, {'b', 'd'}, {'c'}] )`.Wed, 21 Feb 2024 16:47:53 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76142#post-id-76142Comment by licheng for <p>You can represent colorings as (unordered) set partitions of vertices:</p>
<pre><code>from sage.graphs.graph_coloring import all_graph_colorings
G = Graph([('a','b'),('a','d'),('b','c'),('c','d'),('a','c')])
unique_colorings = set( map(SetPartition, all_graph_colorings(G, 3, color_classes=True)) )
for C in unique_colorings:
print(C)
</code></pre>
<p>This tells us that there is just one partition:</p>
<pre><code>{{'a'}, {'b', 'd'}, {'c'}}
</code></pre>
https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76135#post-id-76135Nice. Further, I would like to write a function to determine if a graph is uniquely colorable (i.e. has exactly one (unordered) set partition), it feels a bit wasteful to iterate over all colorings when the graph is not uniquely colorable. I noticed that Python actually doesn't support nested sets, like {{'a'}, {'b', 'd'}, {'c'}}. It shows `TypeError: unhashable type: 'set'` How to do.Wed, 21 Feb 2024 09:54:41 +0100https://ask.sagemath.org/question/76113/how-to-determine-if-two-colorings-of-a-graph-are-the-same/?comment=76135#post-id-76135