6_coloring.py

G = {0:[1, 2, 3, 4],
     1:[0, 2, 4, 5], 
     2:[0, 1, 3, 5], 
     3:[0, 2, 4, 5, 6], 
     4:[0, 1, 3, 5, 6], 
     5:[1, 2, 3, 4, 6], 
     6:[3, 4, 5]
} #example graph in adjacency-lists form

deg_5 = [] #list of vertices with degrees <= 5
for key, val in G.items():
    if len(val) <= 5:
        deg_5.append(key)


def graph_6_coloring(G, deg_5):
    if len(G) <= 6: #if there are no more than 6 vertices, we use 6 color to make coloring
        coloring = {}
        color = 0
        for key in G.keys():
            coloring[key] = color
            color += 1
        return coloring
    else:
        v = deg_5[0]
        deg_5.pop()
        adjacent = G[v] #save vertices connected with v
        for vertex in adjacent:
            vertex = vertex
            G[vertex].remove(v)
            if len(G[vertex]) == 5: #update deg_5
                deg_5.append(vertex)
        del G[v]
        coloring = graph_6_coloring(G, deg_5)
        G[v] = adjacent #after coloring a graph with less vertices, return back vertex v
        deg_5.append(v)
        for vertex in adjacent:
            G[vertex].append(v)
        colors = [coloring[k] for k in adjacent] #list the colors of v-vertex neighbors
        coloring[v] = 0
        while coloring[v] in colors: #search for a color that was not used
            coloring[v] += 1
        return coloring
    
    
coloring = graph_6_coloring(G, deg_5)
print(coloring)

#Check for correctness:
correct_coloring = True
for key, val in G.items():
    for v in val:
        if coloring[key] == coloring[v]:
            correct_coloring = False
            break
print("Coloring is correct:", correct_coloring)