6 ms·

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

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?

dnadler 7y ago
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.
- 2bitencryption 7y ago
  it took me a moment, but now it seems obvious. Thanks :)
kfichter 7y ago
You could simply alternate colors around the node in that case: #%# %x% #%#
andrelaszlo 7y ago
"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 https://en.wikipedia.org/wiki/Four_color_theorem
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
kryptiskt 7y ago
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.
robinhouston 7y ago
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
punnerud 7y ago
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.
meuk 7y ago
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.
- thaumasiotes 7y ago
  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.)
  - deleted 7y ago
    [deleted]
deleted 7y ago
[deleted]

dnadler 7y ago

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.

2bitencryption 7y ago
it took me a moment, but now it seems obvious. Thanks :)

kfichter 7y ago

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

andrelaszlo 7y ago

"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 https://en.wikipedia.org/wiki/Four_color_theorem

deleted 7y ago

[deleted]

deleted 7y ago

[deleted]

kryptiskt 7y ago

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.

robinhouston 7y ago

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

punnerud 7y ago

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.

meuk 7y ago

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.

thaumasiotes 7y ago
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.)
- deleted 7y ago
  [deleted]

deleted 7y ago

[deleted]