TY - JOUR
T1 - A method to obtain lower bounds for circular chromatic number
AU - Yeh, Hong Gwa
PY - 2008/7
Y1 - 2008/7
N2 - 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).
AB - 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).
KW - Acyclic orientation
KW - Circular chromatic number
KW - Lower bounds
KW - Period
KW - Petersen graph
KW - Sink
KW - Source
UR - http://www.scopus.com/inward/record.url?scp=62149146609&partnerID=8YFLogxK
U2 - 10.11650/twjm/1500404993
DO - 10.11650/twjm/1500404993
M3 - 期刊論文
AN - SCOPUS:62149146609
SN - 1027-5487
VL - 12
SP - 997
EP - 1005
JO - Taiwanese Journal of Mathematics
JF - Taiwanese Journal of Mathematics
IS - 4
ER -