Show that if $D$ is a planar directed graph without directed edges going in both ways, then $χA (D) ≤ 3$

Question

I have stuck been with this problem.

I know that the chromatic number in a directe graph $χA (D)$ is defined as the smallest integer such that there is a coloration without monochromatic directed cycles.

But I can't see how this can help me, and I can't find either way a Theorem about planar graphs that could help me

Any help for this?

Answer 1

There are a few main observations that you can tie together to prove this, which I will put in separate spoiler tags (however over box to see the text).

Let $D$ be our asymmetric, directed planar graph. We essentially solve a related problem for $G(D)$, the undirected planar graph formed by taking $D$ and forgetting the directions on its edges.

Observation 1:

If you can divide the vertices of $G(D)$ into 3 sets that do not contain any undirected cycles (ie, 3 induced forests), then you know that $\chi A(D) \leq 3$.

Observation 2:

Every planar graph has a vertex of degree at most 5.

If you're not sure how to tie these together, the basic proof outline is:

Prove you can divide $G(D)$ into 3 or fewer forests, by induction on the number of vertices of $D$. Pull off a vertex $u$ of degree at most 5 from $G(D)$. By the inductive hypothesis, $G(D)-u$ can be divided into 3 forests (some may be empty). Argue you can add $u$ back to the graph and still divide it into 3 forests, by putting $u$ in the right forest of $G(D)-u$ (ie, any forest that $u$ has less than two neighbours in).

{This proof comes from a paper The point arboricity of a graph, by Chartrand, Kronk and Wall}