**2-Coloring Plane
Triangulations**

Myers and Ringel originally conjectured:

**(False) Conjecture:** *Every planar triangulation has a
vertex-2-coloring such that there is no monochromatic triangle and the size of
the two color classes differs by at most one. *

If we 4-color the graph, then merge colors red and green, and merge blue and yellow, then the resulting coloring has no monochromatic triangles. However, it may not satisfy that the two color classes are as equal as possible.

Pascal Ochem (personal communication) reports that the above conjecture is
incorrect. He has constructed a sequence of graphs where the ratio of black to
white vertices is arbitrarily close to 2:1. His constructions start with an
octahedron *G_1* with a fixed face *f*. Form *G_2* as follows: for
each of the 3 faces adjacent to *f*, insert a new degree-three vertex
adjacent with each vertex on the boundary of that face. In this new graph,
repeat the process on the three (new) faces adjacent to *f *to form* G_3*.
Iterate this process to form *G_n*. Two of the three vertices incident
with *f* in *G_n* get the same color. These two vertices lie in *n*
different triangles, which forces the other color to be used repeatedly.

Ochem’s counterexample relies heavily on triangles in *G *that are not
face boundaries. There are still two possible conjectures (the first implies
the second, and so is stronger).

**Conjecture:** *Every planar triangulation has a vertex-2-coloring
such that there is no monochromatic face and the size of the two color classes
differs by at most one. *

**Conjecture:** *Every 4-connected planar triangulation has a
vertex-2-coloring such that there is no monochromatic triangle and the size of
the two color classes differs by at most one. *

**References:**

[MR] P. Myers and G. Ringel, Two color problems, preprint

Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,

Send comments to
*dan.archdeacon@uvm.edu*, and to
*ochem@labri.fr*

December 2003, modified March 2004