Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652600 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics