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

Mickael Montassier 1 Pascal Ochem 2 Alexandre Pinlou 3, *
* Corresponding author
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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?
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00196741
Contributor : Alexandre Pinlou <>
Submitted on : Thursday, December 13, 2007 - 2:24:26 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Identifiers

Citation

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⟩

Share

Metrics

Record views

185