Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths
Résumé
A strong oriented k-coloring of an oriented graph G is a homomorphism f from G to H having k vertices labelled by the k elements of an abelian additive group M, such that for any pairs of arcs uv and zt of G, we have f(v) - f(u) \neq -(f(t) - f(z))$. The strong oriented chromatic number is the smallest k such that G admits a strong oriented k-coloring. In this paper, we consider the following problem: Let i>=4 be an integer. Let G be an oriented planar graph without cycles of lengths 4 to i. What is the strong oriented chromatic number of G?