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 E. Sopena,  Good and semi-strong colorings of oriented planar graphs, Inform. Proc. Letters 51 (1994) 171-174


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003