Strong oriented chromatic number of planar graphs without short cycles
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