Paper Info
Title
Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs.
Abstract
A graph is planar if it can be embedded on the plane without edge-crossings. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). 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 triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239–249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215–219, 2007].
Year
DOI
Venue
2014
10.1016/j.endm.2011.05.022
Graphs and Combinatorics
Keywords
DocType
Volume
Oriented coloring, Planar graph, Girth, 2-Outerplanargraph, Discharging procedure
Journal
30
Issue
ISSN
Citations 
2
1435-5914
2
PageRank 
References 
Authors
0.38
15
2
Name
Order
Citations
PageRank
Pascal Ochem125836.91
Alexandre Pinlou216720.47