Circular (5,2)-coloring of sparse graphs

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)417-426
Number of pages10
JournalSiberian Electronic Mathematical Reports
Volume5
StatePublished - 2008

Keywords

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

Fingerprint

Dive into the research topics of 'Circular (5,2)-coloring of sparse graphs'. Together they form a unique fingerprint.

Cite this