A method to obtain lower bounds for circular chromatic number

研究成果: 雜誌貢獻期刊論文同行評審

2 引文 斯高帕斯(Scopus)


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

頁(從 - 到)997-1005
期刊Taiwanese Journal of Mathematics
出版狀態已出版 - 7月 2008


深入研究「A method to obtain lower bounds for circular chromatic number」主題。共同形成了獨特的指紋。