Strong Oriented Chromatic Number of Planar Graphs without Short CyclesReport as inadecuate




Strong Oriented Chromatic Number of Planar Graphs without Short Cycles - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 ALGCO - Algorithmes, Graphes et Combinatoire LIRMM - Laboratoire d-Informatique de Robotique et de Microélectronique de Montpellier 3 LRI - Laboratoire de Recherche en Informatique

Abstract : Let M be an additive abelian group. An M-strong-oriented coloring of an oriented graph G is a mapping f from VG to M such that fu jv whenever uv is an arc in G and fv−fu −ft−fz 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, 493: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





Author: Mickaël Montassier - Pascal Ochem - Alexandre Pinlou -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents