Oriented 5-coloring of sparse plane graphs

O. V. Borodin, A. O. Ivanova, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)9-17
Number of pages9
JournalJournal of Applied and Industrial Mathematics
Volume1
Issue number1
DOIs
StatePublished - Mar 1 2007

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Oriented 5-coloring of sparse plane graphs'. Together they form a unique fingerprint.

Cite this