Oriented 5-coloring of sparse plane graphs |
| |
| Authors: | O V Borodin A O Ivanova A V Kostochka |
| |
| Institution: | (1) Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia;(2) Institute of Mathematics and Informatics, Ammosov Yakutsk State University, ul. Kulakovskogo 48, Yakutsk, 677000, Russia;(3) University of Illinois, 1409 W.Green St., Urbana, IL 61801, USA |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
