Strong Oriented Chromatic Number of Planar Graphs without Short Cycles

Mickaël Montassier 1, 2 Pascal Ochem 3 Alexandre Pinlou 2, *
* Auteur correspondant
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Let M be an additive abelian group. An M-strong-oriented coloring of an oriented graph G is a mapping f from V(G) to M such that f(u) <> j(v) whenever uv is an arc in G and f(v)−f(u) <> −(f(t)−f(z)) whenever uv and zt are two arcs in G. The strong oriented chromatic number of an oriented graph is the minimal order of a group M such that G has an M-strong-oriented coloring. This notion was introduced by Nesetril and Raspaud [Ann. Inst. Fourier, 49(3):1037-1056, 1999]. We prove that the strong oriented chromatic number of oriented planar graphs without cycles of lengths 4 to 12 (resp. 4 or 6) is at most 7 (resp. 19). Moreover, for all i ≥ 4, we construct outerplanar graphs without cycles of lengths 4 to i whose oriented chromatic number is 7.
Keywords : Graphs Algorithms
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.1-24
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00184811
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 3 juin 2014 - 15:20:47
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mercredi 3 septembre 2014 - 10:35:35

Fichier

455-2688-2-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : lirmm-00184811, version 1

Citation

Mickaël Montassier, Pascal Ochem, Alexandre Pinlou. Strong Oriented Chromatic Number of Planar Graphs without Short Cycles. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.1-24. 〈lirmm-00184811〉

Partager

Métriques

Consultations de la notice

340

Téléchargements de fichiers

193