From: Fred Galvin <galvin@math.ukans.edu>
Subject: Re: Solution to four-color problem
Date: Tue, 11 Jan 2000 23:09:28 -0600
Newsgroups: sci.math
Summary: Hajos conjecture in graph theory

On Wed, 12 Jan 2000, David M Einstein wrote:

> 	Not that I want to confuse the issue, but can you produce a non
> four colorable map conatining a K(3,3) but no K5?  I'm not sure that it
> is impossible, but it seems difficult to get a very complicated graph
> containing a K(3,3) but no K5.

Are you asking about the Hajos conjecture, that every n-chromatic
graph contains a topological K_n? I believe that's true for n <= 4,
false for n >= 7, still open for n = 5 and n = 6, but maybe my
information is out of date.