A method to obtain lower bounds for circular chromatic number

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The circular chromatic number χc(G) of a graph G is a very natural generalization of the concept of chromatic number χ(G), and has been studied extensively in the past decade. In this paper we present a new method for bounding the circular chromatic number from below. Let ω be an acyclic orientation of a graph G. A sequence of acyclic orientations ω1, ω2, ω3, ... is obtained from ω in such a way that ω1 = ω, and ωi (i ≥ 2) is obtained from ωi-1 by reversing the orientations of the edges incident to the sinks of wi-1. This sequence is completely determined by ω, and it can be proved that there are positive integers p and M such that ωi = ωi+p for every integer i ≥ M. The value p at its minimum is denoted by pω. To bound χc(G) from below, the methodology we develop in this paper is based on the acyclic orientations ωM, ωM+1, · · ·, ωM+p ω-1 of G. Our method demonstrates for the first time the possibility of extracting some information about χc(G) from the period ωM, ωM+1, · · ·, ωM+p ω-1 to derive lower bounds for χc(G).

Original languageEnglish
Pages (from-to)997-1005
Number of pages9
JournalTaiwanese Journal of Mathematics
Issue number4
StatePublished - Jul 2008


  • Acyclic orientation
  • Circular chromatic number
  • Lower bounds
  • Period
  • Petersen graph
  • Sink
  • Source


Dive into the research topics of 'A method to obtain lower bounds for circular chromatic number'. Together they form a unique fingerprint.

Cite this