## Abstract

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 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).

Original language | English |
---|---|

Pages (from-to) | 997-1005 |

Number of pages | 9 |

Journal | Taiwanese Journal of Mathematics |

Volume | 12 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2008 |

## Keywords

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