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

Abstract

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
Volume90
Issue number1
DOIs
StatePublished - Jan 2004

Keywords

  • 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

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

Cite this