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 -