The circular chromatic number of a digraph

Drago Bokal, Gašper Fijavž, Martin Juvan, P. Mark Kayll, Bojan Mohar

Research output: Contribution to journalArticlepeer-review

74 Scopus citations

Abstract

We introduce the circular chromatic number χc of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k-cycle has circular chromatic number k/(k - 1), for k ≥ 2, values of χc between 1 and 2 are possible. We show that in fact, χc takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarlly large digirth and circular chromatic number. it is NP-complete to decide if a given digraph has χc at most 2.

Original languageEnglish
Pages (from-to)227-240
Number of pages14
JournalJournal of Graph Theory
Volume46
Issue number3
DOIs
StatePublished - Jul 2004

Keywords

  • Acyclic homomorphism
  • Chromatic number
  • Circular chromatic number
  • Digirth
  • Digraph
  • NP-completeness

Fingerprint

Dive into the research topics of 'The circular chromatic number of a digraph'. Together they form a unique fingerprint.

Cite this