Homomorphisms from sparse graphs with large girth

O. V. Borodin, S. J. Kim, A. V. Kostochka, D. B. West

Research output: Contribution to journalArticlepeer-review


We show that a planar graph with girth at least 20t-2/3 has circular chromatic number at most 2 + 1/t, improving earlier results. This follows from a general result establishing homomorphisms into special targets for graphs with given girth and given maximum average degree. Other applications concern oriented chromatic number and homomorphisms into mixed graphs with colored edges.

Original languageEnglish (US)
Pages (from-to)147-159
Number of pages13
JournalJournal of Combinatorial Theory. Series B
Issue number1
StatePublished - Jan 2004


  • Circular coloring
  • Discharging
  • Graph coloring
  • Graph homomorphism
  • Oriented coloring
  • Planar graph
  • t-nice graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Homomorphisms from sparse graphs with large girth'. Together they form a unique fingerprint.

Cite this