Re:Tetrachromats: people who see colors invisible to most of...
by kragen on Monday November 18, 2019 @05:27PM
(#21568828)
It's correct, as you say, that if we can't build a map that ever requires a fifth colour, then it can't be that there exists a map which requires more than four.
It's just that the C₅-plus-thing requires four colors, even though it doesn't contain any K₄ induced subgraphs. So we could imagine that there might be some larger planar graph that requires 5 colors without containing K₅. As it turns out, there isn't, but that's the thing that's hard to prove.
* It's easy starting from the end, just put one colour in the middle, then alternate second/third colours around the edge until you get back to the start and have to add a fourth. From construction, the worst case is from K1,2 then adding another for K1,3 at which point we need four colours already, but when we add two more on what will be the C5# around they each only connect to one each side and the center. In adding each one you can simply use the colour one hop over on the circumference.
# Since the center of K1,3 must be the center of the final C5-plus-thing, as it already had 3 spokes.