Geodesic
Circular $(5,2)$-coloring of sparse graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 5 (2008), pp. 417-426.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2008_5_a28,
     author = {O. V. Borodin and S. G. Hartke and A. O. Ivanova and A. V. Kostochka and D. B. West},
     title = {Circular $(5,2)$-coloring of sparse graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {417--426},
     publisher = {mathdoc},
     volume = {5},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2008_5_a28/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - S. G. Hartke
AU  - A. O. Ivanova
AU  - A. V. Kostochka
AU  - D. B. West
TI  - Circular $(5,2)$-coloring of sparse graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2008
SP  - 417
EP  - 426
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2008_5_a28/
LA  - en
ID  - SEMR_2008_5_a28
ER  - 
%0 Journal Article
%A O. V. Borodin
%A S. G. Hartke
%A A. O. Ivanova
%A A. V. Kostochka
%A D. B. West
%T Circular $(5,2)$-coloring of sparse graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2008
%P 417-426
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2008_5_a28/
%G en
%F SEMR_2008_5_a28
O. V. Borodin; S. G. Hartke; A. O. Ivanova; A. V. Kostochka; D. B. West. Circular $(5,2)$-coloring of sparse graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 5 (2008), pp. 417-426. http://geodesic.mathdoc.fr/item/SEMR_2008_5_a28/

[1] O. V. Borodin, S.-J. Kim, A. V. Kostochka, and D. B. West, “Homomorphisms from sparse graphs with large girth”, J. Comb. Theory. (B), 90 (2004), 147–159 | DOI | MR | Zbl

[2] O. V. Borodin, A. O. Ivanova, A. V. Kostochka, “Oriented 5-coloring of vertices in sparse graphs”, Diskret. analyz i issled. oper., 13:1 (2006), 16–32 | MR

[3] P. Erdös, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38 | MR | Zbl

[4] A. Galuccio, L. Goddyn, and P. Hell, “High girth graphs avoiding a minor are nearly bipartite”, J. Comb. Theory (B), 83 (2001), 1–14 | DOI | MR

[5] F. Jaeger, “On circular flows in graphs”, Finite and Infinite Sets (Eger, 1981), Colloq. Math. Soc. J. Bolyai, 37, North-Holland, 1984, 391–402 | MR

[6] T. R. Jensen, B. Toft, Graph coloring problems, John–Wiley Sons, New York, 1995 | MR | Zbl

[7] J. Nešetřil and X. Zhu, “On bounded tree-width duality of graphs”, J. Graph Theory, 23 (1996), 151–162 | 3.0.CO;2-L class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[8] W. T. Tutte, “A contribution to the theory of chromatic polinomials”, Canad. J. Math., 6 (1954), 80–91 | MR | Zbl

[9] A. Vince, “Star chromatic number”, J. Graph Theory, 12 (1988), 551–559 | DOI | MR | Zbl

[10] M. DeVos, communication at Workshop on Flows and Cycles, Simon Fraser Univ., June 2000

[11] X. Zhu, “Circular chromatic number of planar graphs of large odd girth”, Electronic J. of Combinatorics, 8:1 (2001), Research Paper 25, 11 pp. | MR | Zbl