Greedy Graph Coloring in Python
PEP 8, the official Python style guide, says that indentation should be 4 spaces per level.  Since whitespace is significant in Python, that is a pretty strong convention.

The implementation could be less verbose:


sorted(list(graph.keys()), …) could be shortened to sorted(graph, …).
Instead of defining available_colors as a list of booleans, you could define taken_colors as a set, ideally using a generator expression.
The loop that assigns color_map[node] can be simplified down to next(generator expression with a condition).




def color_nodes(graph):
    color_map = {}
    # Consider nodes in descending degree 
    for node in sorted(graph, key=lambda x: len(graph[x]), reverse=True):
        neighbor_colors = set(color_map.get(neigh) for neigh in graph[node])
        color_map[node] = next( 
            color for color in range(len(graph)) if color not in neighbor_colors
        )
    return color_map