An Oriented Coloring of Planar Graphs with Girth at Least Five

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 a maximum average degree less than 10/3 and girth at least 5 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. [O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud, É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89].
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 309, pp.2108-2118. 〈10.1016/j.disc.2008.04.030〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371599
Contributeur : Alexandre Pinlou <>
Soumis le : lundi 30 mars 2009 - 07:49:52
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Alexandre Pinlou. An Oriented Coloring of Planar Graphs with Girth at Least Five. Discrete Mathematics, Elsevier, 2009, 309, pp.2108-2118. 〈10.1016/j.disc.2008.04.030〉. 〈lirmm-00371599〉

Partager

Métriques

Consultations de la notice

105