Strong Oriented Chromatic Number of Planar Graphs without Short Cycles - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2008

Strong Oriented Chromatic Number of Planar Graphs without Short Cycles

Résumé

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.

Mots clés

Fichier principal
Vignette du fichier
455-2688-2-PB.pdf (349.93 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt
Loading...

Dates et versions

lirmm-00184811 , version 1 (03-06-2014)

Identifiants

Citer

Mickaël Montassier, Pascal Ochem, Alexandre Pinlou. Strong Oriented Chromatic Number of Planar Graphs without Short Cycles. Discrete Mathematics and Theoretical Computer Science, 2008, Vol. 10 no. 1 (1), pp.1-24. ⟨10.46298/dmtcs.418⟩. ⟨lirmm-00184811⟩
307 Consultations
1731 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More