incremental map coloring
g.r...@iit.cnr.it
colors in such a way adjacent regions have different colors.
I asked myself (after a discussion on polyomino coloring on
it.hobby.enigmi)
how many colors are necessary if, instead of working on all the map,
we are given one region at a time by an adversary and we have
to color each new region at once, without undoing the coloring of the
previous regions.
I also assumed to use a greedy algorithm, that is I color each new
region
with the first color (in a given order) which is suitable.
In this scenario how many colors are needed to color a map?
I put together two pages in which I show that an arbitrary number
of color can be forced.
My subsequent question is: which is the minimal number of
regions in a map that need (in the worst case) K colors?
I found the solution for 5 (easy!) , 6 and 7 colors.
If you are interested in this problem or want just to see the
solutions,
you can visit my two pages starting from here:
http://www.iread.it/map_colors.php
Which is the minimal number of regions to force 8, 9, ...
colors? (I do not know, but if you know, please let me know!)
giovanni
Peter Webb
Giovanni Resta
> Interesting take on an old problem. And a well put together web page on it.
Thanks! I had fun drawing the maps.
I performed an exhaustive (I hope!) search based on the
planar graphs generated by the plantri program
( http://cs.anu.edu.au/~bdm/plantri/ )
by Gunnar Brinkmann and Brendan McKay to find the minimal maps
for 6 and 7 colors (I forgot to add this to the web page).
I have to improve my program somehow to search for the minimal
map for 8 colors. (Or I can search it by hand, but I'm so poor in
visualizing things!)
giovanni
--
http://anagram.it : anagrams, cryptarithms,...
Nick
> It is well known that every map can be colored with just 4
> colors in such a way adjacent regions have different colors.
>
> I asked myself (after a discussion on polyomino coloring on
> it.hobby.enigmi)
> how many colors are necessary if, instead of working on all the map,
> we are given one region at a time by an adversary and we have
> to color each new region at once, without undoing the coloring of the
> previous regions.
I gave a bit of thought to this, in particular to your comment about
needing a deterministic process otherwise you could "win" randomly.
Here's a strategy for the "area drawing" person, that will always defeat
a colourer with 4 pens.
Move one: draw a circle - I call it "the head".
Moves two and three: a circle on each side of the main ones - "the ears"
Move four: an arc that goes from each ear across the top of the head -
"the hair".
The head must be one colour, the hair another, and the ears either one
of two different colours. So for move 5:
If the ears are different colours, just draw a box round the whole
picture - "the frame". That touches all four regions, so can't be
coloured.
If they are the same colour, draw a box ("the background") as though
behind the head - start from the centre of the hair, go up, across, down
outside the ear, across and up to the bottom of the face.
Then do the same final move as above.
This is, unless I'm very much mistaken, I guaranteed winning strategy
for 4 colours. The trick, of course, is that you can beat the
"background" if the ears are different colours (the ear not against the
background can be the same colour as the background) and the "no
background" by having the ears the same colour. But the choice of
whether to have a background or not is made /after/ the ears have been
coloured.
This certainly is an interesting, different, way to think of this old
problem. And the diagrams on your web site are very attractive and
clear - unlike my words above, I'm sure.
--
Online waterways route planner: http://canalplan.org.uk
development version: http://canalplan.eu
Butch Malahide
> It is well known that every map can be colored with just 4
> colors in such a way adjacent regions have different colors.
>
> I asked myself (after a discussion on polyomino coloring on
> it.hobby.enigmi)
> how many colors are necessary if, instead of working on all the map,
> we are given one region at a time by an adversary and we have
> to color each new region at once, without undoing the coloring of the
> previous regions.
>
> I also assumed to use a greedy algorithm, that is I color each new
> region
> with the first color (in a given order) which is suitable.
>
> In this scenario how many colors are needed to color a map?
> I put together two pages in which I show that an arbitrary number
> of color can be forced.
>
> My subsequent question is: which is the minimal number of
> regions in a map that need (in the worst case) K colors?
> I found the solution for 5 (easy!) , 6 and 7 colors.
> If you are interested in this problem or want just to see the
> solutions,
> you can visit my two pages starting from here:http://www.iread.it/map_colors.php
If you want to read more about this subject, try a google search on
"greedy graph coloring" (Painter uses greedy algorithm) or "on-line
graph coloring" (Painter not restricted to using greedy algorithm).
The Qurqirish Dragon
Yes, it is. A similar strategy is listed on the OP's webpage (listed
in the first post) The current question listed there is concerning the
minimal number of regions to force the use of an 8th color. An
algorithm is already listed there which proves that given enough
regions, an arbitrarily large number of colors is needed.
Chip Eastham
I think Nick is trying to generalize Giovanni's
problem by introducing a nondeterministic element
into the coloring. Hence the "ears" in his
illustration may or may not be of the same color.
Although a posteriori a 4 coloring may be given
of any map, by selecting regions based on prior
choices of regions colored, the map-maker is
able to defeat the would-be 4 coloring.
regards, chip
Nick
I am, thanks. The OP says that his strategy works for a deterministic
colourer. I've shown that you can defeat a non-deterministic colourer
every time as well. At least for 4 colours.
Giovanni Resta
> I am, thanks. The OP says that his strategy works for a deterministic
> colourer. I've shown that you can defeat a non-deterministic colourer
> every time as well. At least for 4 colours.
Yes, thanks. I will read your message with attention and
maybe I will add a picture to my web page (citing you as source).
For what concerns greedy graph coloring and on-line graph coloring,
thanks for the hint, Butch.
Indeed I searched with those terms (quite lazily...) but most of
results were about general graphs, while I was interested in planar
ones. I suppose the problem has been studied, but with old results
it is not always easy to find references on-line.
On a Italian newsgroup we have briefly discussed about what can happen
if one restrict the regions to be polyominoes of a given size.
I think I'll try to study the problem a little during the forthcoming
holidays.
giovanni
Chip Eastham
By the way, Giovanni, I meant to say on an earlier
thread, welcome to the newsgroup! Tequila is on
the counter, limes and lemons in the fridge. If
you empty a bottle, get another down off the shelf.
Mind the cat... he's got anger issues.
regards, chip
The Qurqirish Dragon
I see. It is still guaranteed that even a non-deterministic colorer
will be defeated, given any quantity of colors. The MINIMUM size, of
course, is a problem to solve.
Proof that a random colorer can be defeated:
By induction on the number of required colors.
Obviously, by having any two adjacent regions, you can defeat a 1-
coloring.
Now, assume you can defeat a k-coloring, using n regions (with the (n
+1)th region being the one that will require color k+1). Then, there
are fewer than n^k ways to color the n regions successfully with k
colors. Call this number m. Make m+1 non-adjacent copies of the
regions. At least two of them will be colored identically. add the (n
+1)th region to one of those identical copies, and then add a similar
region to another copy, but which also touches the one you just added.
It must use color (k+2), thus defeating a k+1 coloring.
q.e.d.
Now, this obviously makes a huge collection of possibilities very
quickly (at the very least, there are k! recolorings just by permuting
the colors), and so it is almost certainly NOT going to give a minimal
size solution. However, it does give an upper bound.
For example, k=1 is defeated by putting any region adjacent to the
first (2 regions needed)
For k=2, we have n=1. With 2 colors, there are m=2 ways to color the
region. Thus, we create 3 disjoint copies. At least two of these have
the same color (assume color 1). Add a region touching one of these
(since this is how we defeated k=1). It requires color 2. Place
another region touching the second copy and the color 2 region. It
requires color 3. Thus, we can defeat k=2 with 5 regions. (note: we
know that we can defeat it with 3 regions, but the algorithm I listed
wouldn't find it!)
For k=3, we have n=4. There are fewer than m=54 distinct ways to
successfully color the 4 regions in 3 colors (the two adjacent regions
have 6 ways, and the two solitary regions have 3 ways each, but there
are symmetric cases). Thus, we can make 55 copies of this to guarantee
two identical colorings. Then add on the 5th region to one of the
identical ones (this requires color 3), and add on the similar region
to the second of the identical ones, also touching the added one. This
requires color 4, and so we have defeated k=3 with 4*55+2=222 regions.
If you use the fact that k=2 is defeated by (n+1=) 3 adjacent regions,
then there are (m=) 3 distinct ways to color 2 adjacent regions with 3
colors. We make 4 copies of the two-region solution, guaranteeing two
identical copies. Place the 3rd region on one of those (using color
3), and a 3rd on the other which is the same, except for also touching
the color 3 region. This requires color 4, so k=3 is defeated by at
most 2*4+2=10 regions (a vast improvement from the 222 above). Again,
we know that k=3 is defeated by 4 mutually adjacent regions, so we can
get this to be better.
Of course, the basic 4-coloring theorem wells us that k=3 can be
defeated with 4 regions, so this could effectively be used as the base
case.
I'll go one more (defeat k=4) and leave it at that.
For k=4, we look at 3 mutually-adjacent regions. there are 4 distinct
ways to color these with 4 colors (you need 3 different colors,
4C3=4). Thus, if you make 5 copies (15 regions), then a non-
deterministic colorer still must have at least two duplicate
colorings. Add in region 4 to one of these (in the 4th color), and the
similar one to the other copy, extending to touch the 4th color
region. This must be of color 5. So k=4 is defeated in at most 17
regions.
Obviously, if you can find a solution with fewer regions to defeat k
colors, it will make the upper bound on the number of regions smaller.
Using the 6-region solution to defeat k=4 will make the search for the
k=5 upper bound much easier than using the 17-region solution. But at
least the method I listed above does give an upper bound. Efficient
methods in counting effectively identical colorings definitely helps.
Giovanni Resta
> By the way, Giovanni, I meant to say on an earlier
> thread, welcome to the newsgroup! [...]
> Mind the cat... he's got anger issues.
Thanks! By the way when I was a kid I had a siamese
cat with nightly madness moments... It is a miracle I
still have both eyes...
giovanni
Giovanni Resta
> Proof that a random colorer can be defeated:
> By induction on the number of required colors.
>[...]
Thanks for the contribution! I'm waiting for a quiet moment
(forthcoming family reunions make me nervous) to read it carefully
(and possibly make some colorful diagrams...)
giovanni
Mike Terry
news:0bc2e59b-2d8c-4385...@k4g2000yqb.googlegroups.com...
> Proof that a random colorer can be defeated:
> By induction on the number of required colors.
> Obviously, by having any two adjacent regions, you can defeat a 1-
> coloring.
> Now, assume you can defeat a k-coloring, using n regions (with the (n
> +1)th region being the one that will require color k+1). Then, there
> are fewer than n^k ways to color the n regions successfully with k
> colors. Call this number m. Make m+1 non-adjacent copies of the
> regions. At least two of them will be colored identically. add the (n
> +1)th region to one of those identical copies, and then add a similar
> region to another copy, but which also touches the one you just added.
> It must use color (k+2), thus defeating a k+1 coloring.
>
> q.e.d.
I don't follow this - why must it use colour (k+2)?
E.g. 3 colours can be defeated with 3 regions, so we make 28 copies of the 3
regions, which (say) are all coloured the same. Yes, 2 of them are coloured
the same (since they all are). We have only used 3 colours so far, so what
next? No extra region added is going to require 2 more colours...
Mike.
The Qurqirish Dragon
<news.dead.person.sto...@darjeeling.plus.com> wrote:
> "The Qurqirish Dragon" <qurqiri...@aol.com> wrote in messagenews:0bc2e59b-2d8c-4385...@k4g2000yqb.googlegroups.com...
You did note that the procedure is adding *2* more regions, not 1,
right? Obviously 1 region cannot require 2 colors.
3 colors is defeated by 4 regions, not 3. No k can be defeated by
fewer than k+1 regions. But, assuming you meant that the 3 regions is
the defeating solution, with the 4th region removed, we have the
following:
a) At least two of the colorings for your copies are identical.
b) choose two of the identical copies, and add the 3-defeating region
to one of them. This must be color 4.
c) add a region to the other copy that satisfies two conditions:
1) it includes what would be a copy of the 3-defeating region, so
it is also a 3-defeating region.
2) it is adjacent to the region you added in step b
The region added in (c) cannot be color 1, 2 or 3, since it is a 3-
defeating region. It cannot be color 4, since it is adjacent to the
region added in (b). Thus, it must be of color 5, and so you have
constructed a 4-defeating setup.
Mike Terry
No I missed that, although that is exactly what you said! :-)
I get it now...
> 3 colors is defeated by 4 regions, not 3. No k can be defeated by
> fewer than k+1 regions. But, assuming you meant that the 3 regions is
> the defeating solution, with the 4th region removed, we have the
> following:
Yes, I did mean that - because that's the definition you gave! Personally I
think it's more natural to say 4 colours is defeated by 4 regions rather
than 3, but I used your definition. Still, it makes little difference as
long as we agree what k and n are in the proof...
> a) At least two of the colorings for your copies are identical.
> b) choose two of the identical copies, and add the 3-defeating region
> to one of them. This must be color 4.
> c) add a region to the other copy that satisfies two conditions:
> 1) it includes what would be a copy of the 3-defeating region, so
> it is also a 3-defeating region.
> 2) it is adjacent to the region you added in step b
> The region added in (c) cannot be color 1, 2 or 3, since it is a 3-
> defeating region. It cannot be color 4, since it is adjacent to the
> region added in (b). Thus, it must be of color 5, and so you have
> constructed a 4-defeating setup.
Yes, except for a minor flaw - you have assumed that the defeating (n+1)'th
region is on the exterior of the map, and so it can be joined to another
copy of the defeating region. The proof can easily be fixed, by adding the
extra assumption into the inductive hypothesis, and everything still works.
Mike.
The Qurqirish Dragon
<news.dead.person.sto...@darjeeling.plus.com> wrote:
> "The Qurqirish Dragon" <qurqiri...@aol.com> wrote in messagenews:25be98f4-c934-41d1...@s19g2000vbm.googlegroups.com...> On Dec 18, 3:18 pm, "Mike Terry"
I see. I think the simplest thing to add is that if the (n+1)th region
is not on the exterior, then you can find an isomorphic map which
moves it to the outside. Of course, if you ONLY use my procedure (that
is, you don't look for better solutions), then the new region will
always be added on the outside, and so this problem will not appear.