2. Graph Coloring

Pseudo-code

Python code

def has_internal_edge(g, nodeset):
    """
    Check if any pair of nodes in the set nodeset has an
    edge connecting them in g.

    Arguments:
    g -- undirected graph
    nodeset -- subset of nodes in g

    Returns:
    True if there is an edge between any two nodes in nodeset, 
    False otherwise.
    """
    for node in nodeset:
        for nbr in g[node]:
            if nbr in nodeset:
                return True
    return False

def is_three_colorable(g):
    """
    Check if g is three colorable.

    Arguments:
    g -- undirected graph

    Returns:
    True if there is a three coloring of g, False otherwise.
    """
    nodes = set(g.keys())

    # Check all subsets of nodes of size 0 to |V| as red set
    for i in range(len(g)+1):
        for red in itertools.combinations(nodes, i):
            red = set(red)

            # Ensure that there are no edges among nodes in red set
            if not has_internal_edge(g, red):
                # Check all subsets of nodes of size 0 to |V|-|red| as green set
                for j in range(len(g)-i+1):
                    for green in itertools.combinations(nodes - red, j):
                        green = set(green)

                        # Ensure that there are no edges among nodes in green set
                        if not has_internal_edge(g, green):
                            # blue set is the remainder of nodes in the graph
                            blue = nodes - red - green

                            # Ensure that there are no edges among nodes in blue set
                            if not has_internal_edge(g, blue):
                                # sets red, green, blue are a three coloring
                                return True

    # There is no three coloring
    return False