Recursive algorithm for coloring a planar graph in 6 colors.

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]
}
deg_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: #если вершин не больше шести, то для покраски n вершин используем n цветов
        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] #cохраняем вершины, соединённые с v
        for vertex in adjacent:
            vertex = vertex
            G[vertex].remove(v)
            if len(G[vertex]) == 5: #обновление deg_5
                deg_5.append(vertex)
        del G[v]
        coloring = graph_6_coloring(G, deg_5)
        G[v] = adjacent #после покраски графа с меньшим количеством вершин возвращаем v
        deg_5.append(v)
        for vertex in adjacent:
            G[vertex].append(v)
        colors = [coloring[k] for k in adjacent] #составляем список цветов, в которые покрашены соседи v
        coloring[v] = 0
        while coloring[v] in colors: #ищем неиспользованный цвет
            coloring[v] += 1
        return coloring
    
    
coloring = graph_6_coloring(G, deg_5)
print(coloring)

#Проверяем:
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)