An oriented k-coloring of an oriented graph H is defined to be an oriented homomorphism of H into a k-vertex tournament. It is proved that every orientation of a graph with girth at least 5 and maximum average degree over all subgraphs less than 12/5 has an oriented 5-coloring. As a consequence, each orientation of a plane or projective plane graph with girth at least 12 has an oriented 5-coloring.
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering
- Applied Mathematics