Journal of the Australian Mathematical Society

Research Article

On the chromatic number of plane tilings

D. Coulsona1

a1 Department of Mathematics and Statistics, The University of Melbourne, VIC 3010, Australia e-mail: d.coulson@ms.unimelb.edu.au

Abstract

It is known that 4 ≤ x(xs211D2) ≤ 7, where x(xs211D2) is the number of colour necessary to colour each point of Euclidean 2-space so that no two points lying distance 1 apart have the same colour. Any lattice-sublattice colouring sucheme for R2 must use at least 7 colour to have an excluded distance. This article shows that at least 6 colours are necessary for an excluded distance when convex polygonal tiles (all with area greater than some positive constant) are used as the colouring base.

(Received June 17 2002)

(Revised June 25 2003)

2000 Mathematics subject classification

  • primary 05B45;
  • 52C20;
  • secondary 05B40;
  • 52C15