An oriented coloring of planar graphs with girth at least five |
| |
Authors: | Alexandre Pinlou |
| |
Affiliation: | LIRMM - Univ. Montpellier 2, CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France |
| |
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 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]. |
| |
Keywords: | Oriented coloring Planar graph Girth Discharging procedure Maximum average degree |
本文献已被 ScienceDirect 等数据库收录! |
|