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

摘要

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