**Coloring Directed Planar
Graphs**

A *directed graph* is a graph
together with a direction on each edge. A *coloring*
of a directed graph assigns a color *c(**v)* to each
vertex *v*. This defines a mapping form
the set of *arcs* (directed edges) to
ordered pairs of colors. This mapping is *strong*
if no two arcs receive ordered pairs of colors *(c_1,c_2)* and *(c_2,c_1)*. A strong proper coloring of a digraph must have the
underlying graph simple. A strong proper coloring of *G* with *k* colors is
equivalent to an oriented homomorphism of *G*
onto some tournament of order *k.*

**Problem:** *Find the minimum number *k* of
colors such that every planar digraph has a strong proper coloring with *k* colors.
*

Call this minimum the *oriented
chromatic number* of the plane. It is known [RS] that the oriented chromatic
number of the plane is at least 80. An *acyclic
coloring* of an undirected planar graph is a coloring such that no two color
classes induce a cycle. Borodin [B] proved that the acyclic chromatic number of
undirected planar graphs is at most 5. Raspaud proved
that if an undirected graph has an acyclic coloring with *k* colors, then any directed graph on the same edge set has
chromatic number at most *k 2^{k-1}*.
Combining these two results give the upper bound.

It is also known that there is an example of a directed planar graph which requires 16 colors. The gap between the upper bound of 80 and the lower bound of 16 is large.

**References:**

[B] O.V. Borodin, On acyclic coloring of planar
graphs, *Discrete Math.* **25** (1979) 211-236.

[RS] A. Raspaud and *Inform. Proc.
Letters* **51** (1994) 171-174

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

Send comments to *dan.archdeacon@uvm.edu*

December 2003