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

Mickael Montassier 1 Pascal Ochem 2 Alexandre Pinlou 3, *
* Auteur correspondant
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?
Type de document :
Communication dans un congrès
LAGOS: Latin-American Algorithms, Graphs, and Optimization Symposium, Nov 2007, Puerto Varas, Chile. 30, pp.27-32, 2007, Electronic Notes in Discrete Mathematics. 〈http://www.dii.uchile.cl/~lagos07〉. 〈10.1016/j.endm.2008.01.006〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00196741
Contributeur : Alexandre Pinlou <>
Soumis le : jeudi 13 décembre 2007 - 14:24:26
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

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. 30, pp.27-32, 2007, Electronic Notes in Discrete Mathematics. 〈http://www.dii.uchile.cl/~lagos07〉. 〈10.1016/j.endm.2008.01.006〉. 〈lirmm-00196741〉

Partager

Métriques

Consultations de la notice

144