Newsgroups: sci.math
From: william@math.Princeton.EDU (William Schneeberger)
Subject: Re: chromatic number
Date: Fri, 25 Nov 1994 13:21:14 GMT

In article <1994Nov23.042228.13043@galois.mit.edu> tycchow@math.mit.edu (Timothy Y. Chow) writes:
><|> Does anybody know of a theorem similar to the four-color theorem in the case
><|> that sharing a single point also makes two countries adjacent, with the
><|> restriction that at a point at most four countries meet? 
>
>It's pretty easy to construct six regions that are pairwise adjacent, but
>beyond this I don't see any obvious line of attack.

Seven colors suffice.  To see this, we first prove that any map
contains one of

a)	a triangular face
b)	two adjacent vertices of degree 3
c)	a quadrilateral face with a vertex of degree 3.

Suppose you have a map which contains neither a triangle or two
adjacent 3-vertices.  By Euler's equation we have 4V-4E+4F=8.  If we
denote the number of vertices of degree i by v_i, and the number of
faces of i sides by f_i, we get

	4V == 4v_3 + 4v_4 + 4v_5 + 4v_6 + ...
	2E == 3v_3 + 4v_4 + 5v_5 + 6v_6 + ...
	   == 3f_3 + 4f_4 + 5f_5 + 6f_6 + ...
	4F == 4f_3 + 4f_4 + 4f_5 + 4f_6 + ...

Substituting gives

	v_3 - v_5 - 2v_6 - 3v_7 - ... + f_3 - f_5 - 2f_6 - ...
		== 8

By assumption f_3 is zero so we have that

	3v_3 > 3f_5 + 6f_6 + 9f_7 + ... .

Suppose we make a mark at each of the three faces of a 3-vertex.
There will be 3v_3 marks.  Since we are assuming that there are no
pairs of adjacent 3-vertices, the number of marks inside a 5-face is
at most 2, inside a 6-face at most 3, inside a 7-face at most 3, etc.
So the number of marks inside the 4-faces is at least

	3v_3 - 2f_5 - 3f_6 - 3f_7 - 4f_8 - ... > 0.

So there is a quadrilateral with a 3-vertex on it.

Now we prove by induction, first on the number of faces and second on
the number of vertices, that every map is seven-colourable.

Suppose the induction hypothesis, and suppose we have a map with a
triangle.  We may have the following figure:

		  \	      B		  /
		A  \			 /  C
		-----------------------------
		     \		       /
		      \		      /
		       \	     /
			\	    /
		    F	 \	   /	D
			  \	  /
			   \     /
			    \	/
			     \ /
			      *
			     / \
			    /	\
			   /  E	 \

or some of the faces A, C, and E may not exist.  In any case, we can
7-color the map that is missing one of the edges of the triangle by
the induction hypothesis, and we can color the triangle, since there
are at most 6 colors around it.

Now suppose we have a map with two adjacent 3-vertices.  We can shrink
the edge between them to get a 4-vertex instead, and by the inductive
hypothesis, we can 7-color this map.  This leads to a 7-coloring of
the original map.

Finally, suppose we have a quadrilateral with a 3-vertex, i.e.,

		      \		A	|   B
		       \		|
			*---------------+----
			|		|
			|		|
			|		|
		    G	|		|   C
			|		|
			|		|
			|		|
		    ----+---------------+----
			|		|
		    F	|	E	|   D

(again, some of the faces B, D, and F may not exist).  If A and E are
not adjacent, we may delete the top and bottom edges, 7-color the
resulting map, and then, if we color A and E the same color as our
larger face, we get at most 6 colors around the quadrilateral, so we
may 7-color the original map.  A similar argument occurs if C and G
are not adjacent.

If A is adjacent to E and C is adjacent to G, they must be so at a
vertex, in a manner not unlike the following:

		\				/
		 *--+			       /
		 |XX|			      /
		 |XX|			     /
		 +--*		A	+---*
		     \			| XX|
		      \			| XX|
		       \		|B  |
			*---------------+---+
			|		|
			|		|
			|		|
		G	|		|	C
			|		|
			|		|
			|		|
		     +--+---------------+---+
		     | F|		|D  |
		     |X |		| XX|
		     *--+		| XX|
		    /		E	+---*
		 +-*			     \
		 |X|			      \
		 *-+			       \
		/				\

Here the X's indicate regions that may include more than one face, and
the faces A, C, E, and G meet at the point at infinity.  Anyway, we
can 7-color all but the quadrilateral (as proved by deleteing one of
the edges), and then we may permute the colors in the B region, the D
region, and the F region so that, e.g., B, D, and F (or what of them
exist) all have the same color, so that we may seven color the larger
map.

At least this seems to prove it.

So we get that the number of necessary colors is six or seven, and it
looks like attempting to answer the question further is comparable to
trying to solve the four-colour problem.
-- 
Will Schneeberger			Hi There !!
william@math.Princeton.EDU