Oriented 5-coloring of sparse plane graphs

O. V. Borodin; A. O. Ivanova; A. V. Kostochka

doi:10.1134/S1990478907010024

Oriented 5-coloring of sparse plane graphs

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

Mathematics

Research output: Contribution to journal › Article › peer-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 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	https://doi.org/10.1134/S1990478907010024
State	Published - Mar 2007

ASJC Scopus subject areas

Industrial and Manufacturing Engineering
Applied Mathematics

Online availability

10.1134/S1990478907010024

Library availability

Discover UIUC Full Text

Cite this

@article{5a8574f36469411e853916c66f3b83db,

title = "Oriented 5-coloring of sparse plane graphs",

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.",

author = "Borodin, \{O. V.\} and Ivanova, \{A. O.\} and Kostochka, \{A. V.\}",

note = "The authors were supported by the Russian Foundation for Basic Research (projects nos. 03–01– 00796 and 05–01–00816). We are grateful to Aleksei Glebov for useful remarks on the proof.",

year = "2007",

month = mar,

doi = "10.1134/S1990478907010024",

language = "English (US)",

volume = "1",

pages = "9--17",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Pleiades Publishing",

number = "1",

}

TY - JOUR

T1 - Oriented 5-coloring of sparse plane graphs

AU - Borodin, O. V.

AU - Ivanova, A. O.

AU - Kostochka, A. V.

N1 - The authors were supported by the Russian Foundation for Basic Research (projects nos. 03–01– 00796 and 05–01–00816). We are grateful to Aleksei Glebov for useful remarks on the proof.

PY - 2007/3

Y1 - 2007/3

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/38449112627

UR - https://www.scopus.com/pages/publications/38449112627#tab=citedBy

U2 - 10.1134/S1990478907010024

DO - 10.1134/S1990478907010024

M3 - Article

AN - SCOPUS:38449112627

SN - 1990-4789

VL - 1

SP - 9

EP - 17

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

IS - 1

ER -

Oriented 5-coloring of sparse plane graphs

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this