Skip to Main content Skip to Navigation
Reports

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

Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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].
Document type :
Reports
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00186693
Contributor : Alexandre Pinlou <>
Submitted on : Tuesday, February 12, 2008 - 9:52:21 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Thursday, September 23, 2010 - 4:24:04 PM

Identifiers

  • HAL Id : lirmm-00186693, version 3

Collections

Citation

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

Share

Metrics

Record views

205

Files downloads

246