RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., Ser. 1, 2006 Volume 13, Issue 1, Pages 16–32 (Mi da21)

This article is cited in 25 papers

Oriented 5-coloring of sparse plane graphs

O. V. Borodina, A. O. Ivanovab, A. V. Kostochkaac

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Yakutsk State University
c University of Illinois at Urbana-Champaign

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.

UDC: 517.71

Received: 27.09.2005


 English version:
Journal of Applied and Industrial Mathematics, 2007, 1:1, 9–17

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024