Map Coloring

[franktaw at netscape.net]

I've been looking at the following variant of the 4-color theorem
(formerly conjecture) for years, but I've never been able to get
a complete solution.

In the 4-color theorem, we do not consider regions meeting
only at a vertex to touch.  If we were, in general, any number
of colors could be required.

But suppose we limit the number of regions that may join at
any one vertex?  Now, in fact, the number of colors is limited.

The case where at most 4 regions may join at one vertex
(k=4) is of particular interest, both because it is the simplest
extension of the basic problem, and because real-world maps
often do have 4 regions meeting at point, but rarely have more
than 4.  (Note, by the way, that the 4-color theorem is
just the case k=3.)

Given a map with vertices where 4 regions meet, we can
deform it slightly to allow one cross pair or the other to meet:
_|_
 |
to
_|
  \_
   |
and
  |_
_/
 |
Do this independently for each 4-way interesection, and the
result is two "ordinary" planar maps, each of which can be
4-colored.  This shows that the orignal map can be colored
using at most 16 colors.  Clearly, this can be elaborated to
show that the number of colors required is finite for any k.

In fact, using the Euler characteristic, and averaging over
these two variants, there must be a region with less than
6 "average neighbors", where a neighbor sharing an edge
counts as 1, and one sharing a corner counts as 1/2.  (This
is a variant of the technique used to show that 6 colors
suffices for a planar map.)  The maximum number of
neighbors subject to this constraint is 7: a square with
3 4-way vertices and one 3-way vertex.  Thus, we have
shown 8 colors will suffice.

It is fairly easy to construct a map requiring 6 colors: draw
two concentric circles and 3 radii.  It is not hard to show
that 6 is the maximum number of mutually connected
regions under these constraints.  I think 6 colors suffice
for any such map, but I can't prove it.

This, then, is the problem: prove that any map where up
to 4 regions may meet at a vertex can be colored with
6 colors, where regions meeting even at a vertex must
not have the same color.

More generally, when k regions may meet at a vertex, the
maximum number of mutually connected regions is
flloor(3/2 k).  (Set up 3 vertices; have ceiling(k/2) regions
running between one pair, and floor(k/2) between each
of the other pairs.)  Is this the maximum number of colors
required?


A related but distinct problem: what is the maximum
number of colors needed for a vertex coloring of a
graph with a crossing number of k?  Here, k=0 reduces
to the 4 color theorem; and 4^(k+1) is an upper bound.
I haven't really looked at this problem.

Franklin T. Adams-Watters