Title of article :
Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs
Author/Authors :
Ochem، نويسنده , , Pascal and Pinlou، نويسنده , , Alexandre، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Abstract :
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 (1) every oriented triangle-free planar graph has an oriented chromatic number at most 40, and (2) every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bounds of 47 and 67, respectively.
Keywords :
Oriented coloring , Planar graph , girth , 2-outerplanar graph , Discharging procedure
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics