Three-color map coloring

You are given a map as a list of location names, locations, and a list of pairs, adjacencies. Each pair [a, b] means locations a and b share a border.

Implement color_map(locations, adjacencies). It assigns each location one of three colors, "red", "green" or "blue", so that no two bordering locations get the same color.

• Return a dictionary that maps every location to its color, or None if no valid assignment exists.
• Any valid assignment is accepted.
• A location may have no borders. The map may have several disconnected parts.
• Pairs may repeat or appear in both orders. A location that borders itself makes the map impossible.
• Assume up to a few hundred locations. Explain the worst-case running time of your approach.

Example 1

locations   = ["North", "East", "South", "West", "Center"]
adjacencies = [["North","East"], ["East","South"], ["South","West"], ["West","North"],
               ["Center","North"], ["Center","East"], ["Center","South"], ["Center","West"]]

One valid answer: Center -> red, North -> green, East -> blue, South -> green, West -> blue.

Example 2

locations   = ["P", "Q", "R", "S"]
adjacencies = [["P","Q"], ["P","R"], ["P","S"], ["Q","R"], ["Q","S"], ["R","S"]]

Every location borders the other three, so four colors are needed. Return None.

Reconstructed from the reported question; details may differ from what interviewers ask.