Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649735 | Discrete Mathematics | 2009 | 11 Pages |
Abstract
An oriented kk-coloring of an oriented graph GG is a homomorphism from GG to an oriented graph HH of order kk. We prove that every oriented graph with a maximum average degree less than 103 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].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Alexandre Pinlou,