首页 | 本学科首页   官方微博 | 高级检索  
     


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 View the MathML source 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号