Strong oriented chromatic number of planar graphs without short cycles

Abstract

Let M be an additive abelian group. A strong oriented coloringof an oriented graph G is a mapping φ from V(G) to M such that (1) φ(u) ≠ φ(v) whenever uv is an arc in G and (2) φ(v) - φ(u) ≠ -(φ(t) - φ(z)) whenever uv and zt are two arcs in G. We say that G has a M-strong-oriented coloring. The strong oriented chromatic number of an oriented graph, denoted by χ s (G), is the minimal order of a group M, such that G has M-strong-oriented coloring. This notion was introduced by Nešetřil and Raspaud. In this paper, we pose the following problem: Let i ≥ 4 be an integer. Let G be an oriented planar graph without cycles of lengths 4 to i. Which is the strong oriented chromatic number of G ? Our aim is to determine the impact of triangles on the strong oriented coloring. We give some hints of answers to this problem by proving that: (1) the strong oriented chromatic number of any oriented planar graph without cycles of lengths 4 to 12 is at most 7, and (2) the strong oriented chromatic number of any oriented planar graph without cycles of length 4 or 6 is at most 19.