A method to obtain lower bounds for circular chromatic number

作者：Yeh Hong Gwa^*

来源：Taiwanese Journal of Mathematics, 2008, 12(4): 997-1005.

• circular chromatic number
• lower bounds
• acyclic orientation
• sink
• source
• Petersen graph
• period

The circular chromatic number chi(c)(G) of a graph G is a very natural generalization of the concept of chromatic number chi(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 omega be an acyclic orientation of a graph G. A sequence of acyclic orientations omega 1, omega 2, omega 3, ... is obtained from omega in such a way that omega(1) = omega, and omega(i) (i >= 2) is obtained from omega(i-1) by reversing the orientations of the edges incident to the sinks of omega(i-1). This sequence is completely determined by w, and it can be proved that there are positive integers p and M such that omega(i) = omega(i+p) for every integer i >= M. The value p at its minimum is denoted by p(omega). To bound chi(c)(G) from below, the methodology we develop in this paper is based on the acyclic orientations omega m, omega(M+1), ... , omega(M+p omega-1) of G. Our me

• 出版日期2008-7
• 单位中央民族大学