The comment about our similar cityname problem E being a classic NP problem re cliques and colorability is correct. Things to recall to understand this: