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
Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,
Send comments to dan.archdeacon@uvm.edu
December 2003