An oriented coloring of graphs with maximum average degree less that 10/3 - 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 graphs with maximum average degree less that 10/3

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 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 (199.58 Ko) Télécharger le fichier
Loading...

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 3

Citer

Alexandre Pinlou. An oriented coloring of graphs with maximum average degree less that 10/3. RR-07024, 2007. ⟨lirmm-00186693v3⟩
95 Consultations
195 Téléchargements

Partager

Gmail Facebook X LinkedIn More