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., University of Vermont, Burlington, VT 05401-1455 USA

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

December 2003, modified March 2004