An oriented coloring of planar graphs with girth at least five

被引:12
作者
Pinlou, Alexandre [1 ]
机构
[1] Univ Montpellier 2, URMM, CNRS, F-34392 Montpellier 5, France
关键词
Oriented coloring; Planar graph; Girth; Discharging procedure; Maximum average degree; CHROMATIC NUMBER;
D O I
10.1016/j.disc.2008.04.030
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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, AN. Kostochka, J. Nesetril, A. Raspaud, E Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89]. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:2108 / 2118
页数:11
相关论文
共 20 条
[1]  
Borodin OV, 2005, SIB ELECTRON MATH RE, V2, P239
[2]  
Borodin OV, 2005, SIB ELECTRON MATH RE, V2, P222
[3]  
Borodin O.V., 2007, J. Applied and Industrial Math, V1, P9
[4]   On the maximum average degree and the oriented chromatic number of a graph [J].
Borodin, OV ;
Kostochka, AV ;
Nesetril, J ;
Raspaud, A ;
Sopena, E .
DISCRETE MATHEMATICS, 1999, 206 (1-3) :77-89
[5]   THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .6. ON SEVERAL REPRESENTATIONS OF GRAPHS BY RELATIONAL STRUCTURES [J].
COURCELLE, B .
DISCRETE APPLIED MATHEMATICS, 1994, 54 (2-3) :117-149
[6]  
Hell P., 2004, OXFORD LECT SERIES M, V28
[7]  
Kostochka AV, 1997, J GRAPH THEOR, V24, P331, DOI 10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO
[8]  
2-P
[9]   Homomorphism bounds for oriented planar graphs [J].
Marshall, T. H. .
JOURNAL OF GRAPH THEORY, 2007, 55 (03) :175-190
[10]   Antisymmetric flows and strong colourings of oriented graphs [J].
Nesetril, J ;
Raspaud, A .
ANNALES DE L INSTITUT FOURIER, 1999, 49 (03) :1037-+