Re: chromatic number of the plane: open problem

Proginoskes wrote:
David Bernier wrote:
[...]
Is there a graph in the plane with finitely many
vertices and edges between points at unit distance
such that five or more colours are needed to
colour the vertices? (***)

If a graph is planar, then it can be coloured with
four colours, as in the map-colouring problem.

So I think a graph as in (***) needing five
or more colours would be topologically non-planar.
( To be planar, it must be possible to draw the
graph in a plane with non-intersecting edges).

Yes, because the problem of coloring the plane involves a graph which
is highly non-planar. (The edge between (0,0) and (0,1) and the edge
between (-1/2,1/2) and (1/2, 1/2) both cross each other.)

You did forget a theorem proved by Erdos: If the chromatic number of
the plane is k, then there exists a finite subgraph of the "plane
graph" which also requires k colors.


Thanks. I didn't know about that result of Erdos. Concerning
the seven-coloring of the "cells" in the tiling of the
plane by regular hexagons, suppose d is the side of a
hexagon. According to my calculations, any value of d
such that 1/sqrt(7) < d < 1/2 will do.
So if d = 3/7, we have more than one choice of color
for the edges and vertices of the hexagons.

Also, I was wondering if by making d very small, and changing
the coloring, six colors might be enough.

Alternatively, it might be known that a coloring
of the plane with less than seven colors must
be discontinuous on a dense subset of the plane,
or some result that would imply that the coloring
is "impossible" to draw.

I know very little about graph theory, by the way.

David Bernier

.

Relevant Pages

  • Re: Exotic functions (elementary)
    ... A FUNCTION WHOSE GRAPH IS DENSE IN THE PLANE ... nonlinear additive functions can map onto ...
    (sci.math)
  • Re: Mike: One last explanation, I hope!
    ... If I want to make a graph which has an x range that goes from xmin to xmax ... If you want x coordinate zero to be at some position other than the ... Does that make sense for the horizontal plane? ...
    (microsoft.public.vb.general.discussion)
  • chromatic number of the plane: open problem
    ... Problem of chromatic number of the euclidean plane: ... Ron Graham: ``Euclidean Ramsey Theory", ... So D, being at unit distance from B and C, ... By deforming the Moser graph, one can fit it into a plane. ...
    (sci.math)
  • Re: chromatic number of the plane: open problem
    ... Is there a graph in the plane with finitely many ... as in the map-colouring problem. ... or more colours would be topologically non-planar. ...
    (sci.math)