disoriented
Level: Smitemaster

Rank Points: 2384
Registered: 08-07-2007
IP: Logged

Imagine a region of the plane divided up into sub-regions.

By the four-color theorem, a maximum of four colors are required to color the sub-regions so that any adjacent sub-regions are different colors.

However this assumes that sub-regions touching at a corner are not "adjacent".

If corner-touching were considered adjacent, and the number of sub-regions that could touch at any corner is capped at 4, is it still always possible to color the plane with only four colors? If not, what is the new max number of colors required?


____________________________
34th Skywatcher

Best to PM me, since I might miss your message on CaravelNet chat.

---

[Last edited by disoriented at 04-29-2016 12:53 AM]

Pinnacle
Level: Smitemaster

Rank Points: 1129
Registered: 06-10-2004
IP: Logged

It becomes infinite. The simplest case is a pie divided into an arbitrary number of slices. Maybe reading the entire question would have been a good idea.

____________________________
Once (adv.): Enough.
Twice (adv.): Once too often.
~Ambrose Bierce, The Devil's Dictionary

---

[Last edited by Pinnacle at 04-29-2016 02:54 PM]

Dragon Fogel
Level: Smitemaster
Rank Points: 2434
Registered: 06-21-2014
IP: Logged

disoriented wrote:
and the number of sub-regions that could touch at any corner is capped at 4

So slicing a pie into arbitrary numbers of pieces isn't an option here, unless you mean something different from what I think you mean.

It's easy to come up with an example where five colors are needed. Take four regions touching at a corner; they all have to be different colors. Now make a region that's a big ring touching all four of these. It has to be a different color from each of them, so five colors are needed.

I'm not sure if five would be sufficient for any map, though. I guess if I were trying to prove it, I'd show that you can transform any four-color map made without considering the corner rule into a five-color map that obeys it. But I'm not sure where to begin on that.

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

Divide that extra 'ring' in half and you get 6 regions all of which touch each other, therefore requiring 6 colours:

 _______
|  _ _  |
|_|_|_|_|
| |_|_| |
|_______|

Six suffices as well. The only points of interest are those which indeed touch four corners. Consider what happens if you adjust one of the regions slightly so you no longer have them all touching:

 _ _ 
|_|_|
|_|_|

 _ _ 
|_|_|
|_\_|

The only difference in the second map is that the lower left and upper right regions no longer touch.

To get from the lower map to the upper map we add one extra connection. If we talk about things in terms of a graph instead (a vertex per region, edges between vertices if those regions touch), we're adding one extra edge that crosses at most one existing edge.

This makes the graph 1-planar: https://en.wikipedia.org/wiki/1-planar_graph#Coloring

---

[Last edited by TripleM at 04-29-2016 04:07 AM]

Someone Else
Level: Smitemaster

Rank Points: 1300
Registered: 06-14-2005
IP: Logged

Not quite; this is a subset of all 1-planar graphs. But it's possible that there exists no planar graph whose dual's largest clique is degree 4 or less which is 1-planar and requires 7 colours.

As it's late and I can't think of one right now, I'll just say that we know that the maximum is either 6 or 7 colours.

---

[Last edited by Someone Else at 04-29-2016 05:58 AM]

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

I'm not sure what you mean - all 1-planar graphs can be colored with 6 colors.

Someone Else
Level: Smitemaster

Rank Points: 1300
Registered: 06-14-2005
IP: Logged

Ah, I see my reading comprehension skills are poor. Yeah, you're right.