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].
Type de document :
Rapport
RR-07024, 2007
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00186693
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 12 février 2008 - 09:52:21
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 16:24:04

Fichier

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

133

Téléchargements de fichiers

135