An Oriented Coloring of Planar Graphs with Girth at Least Five - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport Année : 2007

An Oriented Coloring of Planar Graphs with Girth at Least Five

Résumé

An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented graph with maximum average degree strictly less than 10/3 has an oriented chromatic number at most 16. This implies that every oriented planar graph with girth at least 5 has an oriented chromatic number at most 16, that improves the previous known bound of 19 due to Borodin et al. [Borodin, O. V. and Kostochka, A. V. and Nesetril, J. and Raspaud, A. and Sopena, E., On the maximum average degree and the oriented chromatic number of a graph, Discrete Math., 77–89, 206, 1999].
Fichier principal
Vignette du fichier
pin07.pdf (272.32 Ko) Télécharger le fichier

Dates et versions

lirmm-00186693 , version 1 (11-11-2007)
lirmm-00186693 , version 2 (01-02-2008)
lirmm-00186693 , version 3 (12-02-2008)

Identifiants

  • HAL Id : lirmm-00186693 , version 1

Citer

Alexandre Pinlou. An Oriented Coloring of Planar Graphs with Girth at Least Five. RR-07024, 2007. ⟨lirmm-00186693v1⟩
95 Consultations
195 Téléchargements

Partager

Gmail Facebook X LinkedIn More