Colorings and girth of oriented planar graphs (Q1356774)

Let \(G=(V,E)\) and \(H=(V',E')\) be graphs (possibly digraphs). A homomorphism from \(G\) to \(H\) is any mapping \(f:V\to V'\) satisfying \([x,y]\in E\Rightarrow [f(x),f(y)]\in E'.\) Here the brackets on both sides of the implication mean the same thing: either an edge or an arc. The existence of a homomorphism from \(G\) to \(H\) is denoted by \(G\to H\). The following two problems are considered: (A) The oriented coloring problem. Given an oriented graph \(G=(V,A)\), find the smallest number of vertices of an oriented graph \(H\) for which \(G\to H\). This number, denoted by \(\chi(\vec G)\), is called the oriented chromatic number of \(G\). (Note that this is the same as the ordinary chromatic number if we consider symmetric digraphs as target digraphs.) (B) The girth problem. Given an integer \(g>2\), determine the quantity \[ \chi(\vec g)= \max\{\chi(\vec G)\mid G\text{ is planar and has girth }g\}. \] It is shown that every orientation of any large girth planar graph has oriented chromatic number at most 5. Furthermore, the authors classify those digraphs on 3, 4 and 5 vertices which color (i.e. admit a homomorphism from) all large girth oriented planar graphs.