Hacker News Reader

aha, so infinities are not allowed. Fair enough, in that case the gray pixel needs to be filled with one of the colours and the two colours connected to that specific one become interchangeable.

View on HN

The four colour theorem does generalize to infinite planar graphs, in the sense that if an infinite graph can be embedded in the plane without overlaps, then a four-colouring is possible. It's a straightforward consequence of the compactness theorem for propositional logic, which I set as an exercise for my students when I teach the topic.

so in essence there is an additional constraint, that each touching edge has to be of a given minimal size. Each contiguous "blob" with a given circumference of N * this minimal size, can only connect to at most N other blobs.

No, there is no minimal size, just that we only consider two regions as being "in contact" and therefore requiring different colours) if they have a shared boundary, and that boundary is of non-zero length.

There is no limit to how many regions can surround and be in contact with a given region, it's just that the shared border that defines "in contact with" must be of non-zero length.

Note also: we are dealing with finite maps. That means that for any given map there will be a shortest boundary for that map, but it doesn't mean there is a minimum constraint.

Reply on news.ycombinator.com