A method to obtain lower bounds for circular chromatic number

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 ω₁, ω₂, ω₃, ... is obtained from ω in such a way that ω₁ = ω, and ω_i (i ≥ 2) is obtained from ω_i-1 by reversing the orientations of the edges incident to the sinks of w_i-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).