Coloring

• Algorithms for coloring quadtrees.

• Aperiodic colored tilings, F. Gähler. Also available in postscript.

• The chromatic number of the plane. Gordon Royle and Ilan Vardi summarize what's known about the famous open problem of how many colors are needed to color the plane so that no two points at a unit distance apart get the same color. See also another article from Dave Rusin's known math pages.
  

• Coloring line arrangements. The graphs formed by overlaying a collection of lines require three, four, or five colors, depending on whether one allows three or more lines to meet at a point, and whether the lines are considered to wrap around through infinity. Stan Wagon asks similar questions for unit circle arrangements.
  

• The Four Color Theorem. A new proof by Robertson, Sanders, Seymour, and Thomas.

• Geometric graph coloring problems from "Graph Coloring Problems" by Jensen and Toft.
  

• Infect. Eric Weeks generates interesting colorings of aperiodic tilings.

• Plane color. How big can the difference between the numbers of black and white regions in a two-colored line arrangement? From Stan Wagon's PotW archive.

• Puzzles by Eric Harshbarger, mostly involving colors of and mazes on polyhedra and polyominoes.

• Rec.puzzles archive: coloring problems.

• Solution to problem 10769. Apparently problems of coloring the points of a sphere so that orthogonal points have different colors (or so that each set of coordinate basis vectors has multiple colors) has some relevance to quantum mechanics; see also papers quant-ph/9905080 and quant-ph/9911040 (on coloring just the rational points on a sphere), as well as this four-dimensional construction of an odd number of basis sets in which each vector appears an even number of times, showing that one can't color the points on a four-sphere so that each basis set has exactly one black point.

• Three-color the Penrose tiling? Mark Bickford asks if this tiling is always three-colorable. Ivars Peterson reports on a new proof by Tom Sibley and Stan Wagon that the rhomb version of the tiling is 3-colorable; A proof of 3-colorability for kites and darts was recently published by Robert Babilon [Discrete Mathematics 235(1-3):137-143, May 2001]. This is closely related to my page on line arrangement coloring, since every Penrose tiling is dual to a "multigrid", which is just an arrangement of lines in parallel families. But my page only deals with finite arrangements, while Penrose tilings are infinite.

• Three nice pentomino coloring problems, Owen Muniz.

From the Geometry Junkyard, computational and recreational geometry pointers.
Send email if you know of an appropriate page not listed here.
David Eppstein, Theory Group, ICS, UC Irvine.
Semi-automatically filtered from a common source file.