naive_5_coloring.py

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

deg_5 = [] #list of vertices with degree <= 5
for key, val in G.items():
    if len(val) <= 5:
        deg_5.append(key)
is_end = False #flag that corresponds to a case when there is a cycle of odd length
 
 
def dfs(G, coloring, c1, c2, current_v, v):
    global is_end
    if is_end:
        return coloring
    coloring[current_v] = c1
    for vertex in G[current_v]:
        if vertex == v and coloring[v] == c1:
            is_end = True
        elif not is_end and coloring[vertex] == c1:
            coloring = dfs(G, coloring, c2, c1, vertex, v)
    return coloring


def graph_5_coloring(G, deg_5):
    global is_end
    if len(G) <= 5: #if there are no more than 5 vertices we use 5 colors:
        coloring = {}
        color = 0
        for key in G.keys():
            coloring[key] = color
            color += 1
        return coloring
    else:
        v = deg_5[-1] #choose a vertex with degree <=5
        deg_5.pop()
        adjacent = G[v] #save vertices connected to 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_5_coloring(G, deg_5)
        G[v] = adjacent #after coloring a smaller graph, return v
        deg_5.append(v)
        for vertex in adjacent:
            G[vertex].append(v)
        colors = [coloring[k] for k in adjacent] #collect list of colors that are used for neighbors of v
        vertex_color = 0
        while vertex_color in colors and vertex_color < 5:
            vertex_color += 1
        if vertex_color < 5: #if there were used <= 4 colors for neighbors, than use a free color
            coloring[v] = vertex_color
            return coloring
        for c1 in [0, 4]: #if not, check for a color that can be used for v
            for c2 in [1, 2, 3]:
                is_end = False
                recoloring = dfs(G, coloring, c1, c2, v, v)
                if not is_end:
                    return recoloring

    
coloring = graph_5_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)