[blevin]

Your example adds more constraints than the original problem, by pre-assigning colors to regions and then asking how to solve for the black region.

In the original problem statement, you could solve by re-assigning your green region to be orange, your red region to be blue, your black region to green, and the white regions to red. Also note that regions that meet at a single point (as in your example) are not considered to be adjacent.

[Phemist]

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.

[fnrslvr]

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.

[Phemist]

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.

[ColinWright]

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.