Hacker News Reader

Comment by 2bitencryption | Hacker News Reader

I've heard vaguely of the coloring problems before, but this one quote is confusing me, can someone explain what I'm missing?

> Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering).

But what if my "map" includes a node that has more than four neighbors? If there are only four colors, then one of the neighbors must be pidgeon-holed to share a color with the node? Are there constraints on how many neighbors a node can have?

View on HN

I’m not sure exactly what situation you’re imagining. But as an illustrative example, if the central node has eight neighbors that are connected to each other in a cycle, the graph can be coloured with three colours like this:

  2 -- 3 -- 2
  | \  |  / |
  |  \ | /  |
  3 -- 1 -- 3
  |  / | \  |
  | /  |   \|
  2 -- 3 -- 2

"In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet."

https://en.wikipedia.org/wiki/Four_color_theorem

You could simply alternate colors around the node in that case:

  #%#
  %x%
  #%#

No, it doesn't have to share a color with a neighbor. The neighbors don't have to be neighbors to each other and can share colors.

The constraint is not on the number of neighbors directly. If there is just one node (say, A) with 4 neighbors (say B1, B2, B3, B4), we can color A red and B1, B2, B3, B4 blue. It only becomes a problem when all nodes are interconnected (i.e. the graph is complete). So, the result does imply that graphs which are not colorable with 4 colors are not planar. In particular, the complete graph (where all nodes of the graph are connected) with 4 nodes is not planar.

The complete graph with 4 nodes is planar, and obviously can be colored with only 4 colors -- that gives every node a unique color.

The complete graph with 5 nodes is what isn't planar. (That, and the complete bipartite graph with 3 nodes on each side.)

Think of a hypothetical earth:

1.The poles was each their own country with a color on the map

2. Every country stretch all the way from south to north

Every country in 2. then only need two colors. Because the “same” color can never meet in any point.

The fourth color comes into play if you have a new country that bridge the south (or north) and both of the countries in step 2. at the same time.

In your example the middle node could be green, and the nodes it shares edges with could alternate between red, blue and yellow as you iterate over them.

it took me a moment, but now it seems obvious. Thanks :)

Reply on news.ycombinator.com