Mickael Montassier ; Pascal Ochem ; Alexandre Pinlou - Strong Oriented Chromatic Number of Planar Graphs without Short Cycles

dmtcs:418 - Discrete Mathematics & Theoretical Computer Science, January 10, 2008, Vol. 10 no. 1 - https://doi.org/10.46298/dmtcs.418
Strong Oriented Chromatic Number of Planar Graphs without Short CyclesArticle

Authors: Mickael Montassier 1,2; Pascal Ochem ORCID3; Alexandre Pinlou ORCID2

  • 1 Laboratoire Bordelais de Recherche en Informatique
  • 2 Algorithmes, Graphes et Combinatoire
  • 3 Laboratoire de Recherche en Informatique

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.


Volume: Vol. 10 no. 1
Published on: January 10, 2008
Imported on: March 26, 2015
Keywords: Graphs,Algorithms,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 412 times.
This article's PDF has been downloaded 402 times.