Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2007

Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths

Abstract

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?

Dates and versions

lirmm-00196741 , version 1 (13-12-2007)

Identifiers

Cite

Mickael Montassier, Pascal Ochem, Alexandre Pinlou. Strong Oriented Chromatic Number of Planar Graphs without Cycles of Specific Lengths. LAGOS: Latin-American Algorithms, Graphs, and Optimization Symposium, Nov 2007, Puerto Varas, Chile. pp.27-32, ⟨10.1016/j.endm.2008.01.006⟩. ⟨lirmm-00196741⟩
97 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More