### Strong oriented chromatic number of planar graphs without short cycles

*Mickaël Montassier, Pascal Ochem, Alexandre Pinlou*

#### Abstract

Let M be an additive abelian group. A *strong
oriented coloring* of 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.

Full Text: PDF PostScript