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.
|Original language||English (US)|
|Number of pages||9|
|Journal||Journal of Applied and Industrial Mathematics|
|State||Published - Mar 2007|
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering
- Applied Mathematics