Reports Year : 2007

An oriented coloring of graphs with maximum average degree less that 10/3

Abstract

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 and versions

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

Identifiers

  • HAL Id : lirmm-00186693 , version 3

Cite

Alexandre Pinlou. An oriented coloring of graphs with maximum average degree less that 10/3. RR-07024, 2007. ⟨lirmm-00186693v3⟩
114 View
221 Download

Share

More