Oriented chromatic number of planar graphs

Definitions and mathematical statement

An oriented graph is obtained from a finite simple undirected graph by choosing exactly one direction for each edge. In particular it has neither loops nor a pair of opposite arcs. An oriented $k$-coloring is a map $c:V\to\{1,\ldots,k\}$ with two properties: endpoints of every arc have different colors, and whenever $u\to v$ and $x\to y$ are arcs with $c(u)=c(y)$, one has $c(v)\ne c(x)$. Thus arcs between any two color classes, if present, all point in the same direction.

The oriented chromatic number $\chi_o(D)$ is the least $k$ admitting such a coloring. Equivalently, it is the least order of an oriented graph receiving a vertex homomorphism from $D$, where a homomorphism sends each arc to an arc of the same direction. The target may be completed to a tournament without harming a homomorphism.

The problem is to determine the exact universal value \[ P=\sup\{\chi_o(D):\text{the underlying undirected graph of }D \text{ is planar}\}. \] The supremum ranges over every finite planar graph and every orientation of its edges. It is not the minimum over orientations of each graph. A complete answer must supply a uniform upper bound and a matching lower construction, or establish unboundedness if no finite upper bound exists. The target graph for the homomorphism may vary with $D$; a single common tournament is not required by this definition.

Short English statement

Determine the largest oriented chromatic number obtainable by orienting the edges of a finite planar graph.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3228 (OPG-494), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Oriented chromatic number of planar graphs. Original problem and discussion. http://www.openproblemgarden.org/op/oriented_chromatic_number_of_planar_graphs.