O. V. Borodin, S. G. Hartke, A. O. Ivanova, A. V. Kostochka, D. B. West, “Circular <nobr>$(5,2)$</nobr>-coloring of sparse graphs”, Sib. Èlektron. Mat. Izv., 2008, Volume 5,Pages <nobr>417

This article is cited in 12 papers

Research papers

Circular $(5,2)$-coloring of sparse graphs

O. V. Borodin^a, S. G. Hartke^b, A. O. Ivanova^c, A. V. Kostochka^a, D. B. West^b

^a Sobolev Institute of Mathematics, Novosibirsk, Russia
^b University of Illinois, Urbana, USA
^c Yakutsk State University

Abstract: We prove that every triangle-free graph whose subgraphs all have average degree less than $\frac{12}5$ has a circular $(5,2)$-coloring. This includes planar and projective-planar graphs with girth at least $12$.

Keywords: triangle-free graph, circular $(k,d)$-coloring, projective-planar graph.

UDC: 519.172.2

MSC: 05С15

Received August 14, 2008, published October 29, 2008

Language: English