Abstract
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) |
---|---|
Pages (from-to) | 9-17 |
Number of pages | 9 |
Journal | Journal of Applied and Industrial Mathematics |
Volume | 1 |
Issue number | 1 |
DOIs | |
State | Published - Mar 2007 |
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering
- Applied Mathematics