Article ID Journal Published Year Pages File Type
4652656 Electronic Notes in Discrete Mathematics 2008 6 Pages PDF
Abstract

A strong oriented k-coloring of an oriented graph G is a homomorphism ϕ 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 and of G, we have ϕ(v)−ϕ(u)≠−(ϕ(t)−ϕ(z)). The strong oriented chromatic number χs(G) 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?

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics