Color coding the colorings dictionary in graph_colorings

asked 2022-06-07 14:10:46 +0200

vidyarthi
167 ●1 ●3 ●15

updated 2022-06-10 11:11:50 +0200

Suppose I color the vertices of a graph properly, and I wish to obtain the color code for each vertex, where color code for each vertex is defined as a tuple of the color of the vertex along with number of neighbors corresponding to each color to some vertex. How do I get at that? Will all_graph_colorings or first_coloring help in that: Some pseudo code using first_coloring beginning would be:

 from sage.graphs.graph_coloring import first_coloring
 G = graphs.WheelGraph(5)
 d=first_coloring(G, 5)
 l=[]
 for i in G.vertices():
      for j in G.neighbors(i):
           l.append(d[i],d[j])
 return l

In the above code, I think there are several problems. First of all, the first_coloring does not cover all possible colorings and is a list and not a dictionary. The all_graph_colorings though gives a dictionary, but I am unsure of how to access the elements there. Next, the double iteration might not produce the tuple that I want as I have mentioned only pairs to be appended to the list l. Again, on running the code, I get the error append method only takes one argument and two are given. How do I fix that? The color code concept is inspired from the irregular chromatic number of the graph explained in some detail here. Any ideas? Thanks beforehand.

answered 2022-06-08 03:36:23 +0200

Max Alekseyev

5671 ●5 ●36 ●121

updated 2022-06-10 17:55:55 +0200

The question is quite fuzzy and here is my best guess for interpreting it:

from sage.graphs.graph_coloring import first_coloring
G = graphs.WheelGraph(5)
d=first_coloring(G, 5)
d_set = [set(c) for c in d]  # color classes as sets

color_code = {}
for i in G.vertices():
    col = next(k for k in range(len(d_set)) if i in d_set[k]) # color of i as index in d_set
    N = set(G.neighbors(i))
    color_code[i] = (col, tuple(len(N & c) for c in d_set))

print(color_code)

Is this what you want?

ADDED. Similarly we can compute color code for each of the colorings:

from sage.graphs.graph_coloring import all_graph_colorings
G = Graph({0: [1, 2, 3], 1: [2]})
G = graphs.WheelGraph(5)

for m,d in enumerate(all_graph_colorings(G,5)):
    d_set = [set(c) for c in d.values()]

    color_code = {}
    for i in G.vertices():
        col = next(k for k in range(len(d_set)) if i in d_set[k]) 
        N = set(G.neighbors(i))
        color_code[i] = (col, tuple(len(N & c) for c in d_set))

    print(f'coloring # {m}\tcode: {color_code}')

edit flag offensive delete link

Comments

Thanks! This is what I wanted. But, I have some questions. Like, when I give the parameter of first_coloring as (G,2) I still get a valid code. I should actually get an error that such a coloring does not exist right. Or, is the first_coloring function not a proper coloring function, The second question is, the first_coloring function works for only one coloring of vertices. What if the color codes of two adjacent vertices are same in one proper coloring of vertices but different in another coloring with same number of colors. How do I iterate over all possible colorings using the same number of colors.

vidyarthi ( 2022-06-10 10:49:18 +0200 )edit

The documentation for first_coloring says that it returns "first found coloring with at least n colors." So, it can increase the given number of colors if needed and always will find some coloring.

As for iterating over all colorings, I've added a code that does that.

Max Alekseyev ( 2022-06-10 17:58:38 +0200 )edit

Note that ticket #33554 fixes method all_graph_colorings to ensure that it returns only colorings using exactly the prescribed number of colors (if any). It also clarifies the fact that the given number of colors in method first_coloring is a lower bound on the number of colors of the returned coloring.

Help reviewing ticket #33554 is welcome.

David Coudert ( 2022-06-11 09:29:48 +0200 )edit

add a comment

Your Answer

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

Color coding the colorings dictionary in graph_colorings

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Color coding the colorings dictionary in graph_colorings edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Color coding the colorings dictionary in graph_colorings