Discrete Mathematics & Theoretical Computer Science, Vol 10, No 1 (2008)

Font Size:  Small  Medium  Large

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