class Graph_Coloring:

    colors = []

    nodes = [0, 1, 2, 3]

    graph = {0: [1, 2],
             1: [0, 2, 3],
             2: [0, 1, 3],
             3: [1, 2]
             }

    solution = {}

    def __init__():
        ch = 'a'
        while True:
            Graph_Coloring.colors.append(ch)
            print("Colors: "+str(len(Graph_Coloring.colors)))
            satisfied = Graph_Coloring.main()

            if satisfied == True:
                print(Graph_Coloring.solution)
                exit()
            else:
                print("Cannot do coloring with "+str(len(Graph_Coloring.colors))+" colors")
                ch = chr(ord(ch) + 1)

    def check(node, color):
        for neighbor in Graph_Coloring.graph.get(node):
            color_of_neighbor =Graph_Coloring.solution.get(neighbor)
            if color_of_neighbor == color:
                return False

        return True

    def set_node_color(node):
        for color in Graph_Coloring.colors:
            if Graph_Coloring.check(node, color):
                return color

    def main():
        for node in Graph_Coloring.nodes:
            if Graph_Coloring.set_node_color(node) == None:
                return False
            else:
                Graph_Coloring.solution[node] = Graph_Coloring.set_node_color(node)
        return True

Graph_Coloring.__init__()