Circular (5,2)-coloring of sparse graphs

O. V. Borodin; S. G. Hartke; A. O. Ivanova; A. V. Kostochka; D. B. West

Circular (5,2)-coloring of sparse graphs

O. V. Borodin, S. G. Hartke, A. O. Ivanova, A. V. Kostochka, D. B. West

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that every triangle-free graph whose subgraphs all have average degree less than 12/5 has a circular (5; 2)-coloring. This includes planar and projective-planar graphs with girth at least 12.

Original language	English (US)
Pages (from-to)	417-426
Number of pages	10
Journal	Siberian Electronic Mathematical Reports
Volume	5
State	Published - 2008

Keywords

triangle-free graph
projective-planar graph
circular (k; d)-coloring

Library availability

Discover UIUC Full Text

Cite this

@article{c088776bd5ad4b9b8e4c63f8443ec81f,

title = "Circular (5,2)-coloring of sparse graphs",

abstract = "We prove that every triangle-free graph whose subgraphs all have average degree less than 12/5 has a circular (5; 2)-coloring. This includes planar and projective-planar graphs with girth at least 12.",

keywords = "triangle-free graph, projective-planar graph, circular (k; d)-coloring",

author = "Borodin, {O. V.} and Hartke, {S. G.} and Ivanova, {A. O.} and Kostochka, {A. V.} and West, {D. B.}",

year = "2008",

language = "English (US)",

volume = "5",

pages = "417--426",

journal = "Siberian Electronic Mathematical Reports",

issn = "1813-3304",

publisher = "Sobolev Institute of Mathematics",

}

TY - JOUR

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

AU - Borodin, O. V.

AU - Hartke, S. G.

AU - Ivanova, A. O.

AU - Kostochka, A. V.

AU - West, D. B.

PY - 2008

Y1 - 2008

N2 - We prove that every triangle-free graph whose subgraphs all have average degree less than 12/5 has a circular (5; 2)-coloring. This includes planar and projective-planar graphs with girth at least 12.

AB - We prove that every triangle-free graph whose subgraphs all have average degree less than 12/5 has a circular (5; 2)-coloring. This includes planar and projective-planar graphs with girth at least 12.

KW - triangle-free graph

KW - projective-planar graph

KW - circular (k; d)-coloring

M3 - Article

SN - 1813-3304

VL - 5

SP - 417

EP - 426

JO - Siberian Electronic Mathematical Reports

JF - Siberian Electronic Mathematical Reports

ER -

Circular (5,2)-coloring of sparse graphs

Abstract

Keywords

Library availability

Fingerprint

Cite this