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

asked 2024-02-20 11:32:41 +0100

licheng
299 ●4 ●22 ●40

updated 2024-02-20 11:52:53 +0100

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.

answered 2024-02-20 18:34:21 +0100

Max Alekseyev

6488 ●9 ●47 ●153

updated 2024-02-20 18:37:32 +0100

You 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'}}

edit flag offensive delete link

Comments

Nice. 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.

licheng ( 2024-02-21 09:54:41 +0100 )edit

Hashable 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'}] ).

Max Alekseyev ( 2024-02-21 16:47:53 +0100 )edit

Thank 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.

licheng ( 2024-02-21 18:52:26 +0100 )edit

I've already provided code for computing unique_colorings - just check len(unique_colorings) == 1 to make sure that there is one and only coloring.

Max Alekseyev ( 2024-02-21 21:47:27 +0100 )edit

I 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 codes

licheng ( 2024-02-22 01:43:22 +0100 )edit

add a comment

Your Answer

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

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

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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