O. V. Borodin, S. G. Hartke, A. O. Ivanova, A. V. Kostochka, D. B. West, “Circular $(5,2)$-coloring of sparse graphs”, Сиб. электрон. матем. изв., 2008, том 5,страницы 417

Эта публикация цитируется в 12 статьях

Статьи

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

Аннотация: 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$.

Ключевые слова: triangle-free graph, circular $(k,d)$-coloring, projective-planar graph.

УДК: 519.172.2

MSC: 05С15

Поступила 14 августа 2008 г., опубликована 29 октября 2008 г.

Язык публикации: английский