TY - JOUR
T1 - On the fractional chromatic number, the chromatic number, and graph products
AU - Klavžar, Sandi
AU - Yeh, Hong Gwa
N1 - Funding Information:
∗Corresponding author. E-mail addresses: [email protected] (S. Klavz'ar), [email protected] (H.-G. Yeh). 1Supported by the Ministry of Science and Technology of Slovenia under the Grant 101-504. 2Supported in part by the National Science Council under Grant NSC 89-2115-M008-008.
PY - 2002/3/28
Y1 - 2002/3/28
N2 - It is shown that the difference between the chromatic number # and the fractional chromatic number yj can be arbitrarily large in the class of uniquely colorable, vertex transitive graphs. For the lexicographic product Go H it is shown that χ(GoH) > χf(G)χ(H). This bound has several consequences, in particular, it unifies and extends several known lower bounds. Lower bounds of Stahl (for general graphs) and of Bollobds and Thomason (for uniquely colorable graphs) are also proved in a simple, elementary way.
AB - It is shown that the difference between the chromatic number # and the fractional chromatic number yj can be arbitrarily large in the class of uniquely colorable, vertex transitive graphs. For the lexicographic product Go H it is shown that χ(GoH) > χf(G)χ(H). This bound has several consequences, in particular, it unifies and extends several known lower bounds. Lower bounds of Stahl (for general graphs) and of Bollobds and Thomason (for uniquely colorable graphs) are also proved in a simple, elementary way.
KW - Chromatic number
KW - Fractional chromatic number
KW - Graph product
KW - Uniquely colorable graph
UR - http://www.scopus.com/inward/record.url?scp=31244431634&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(01)00312-0
DO - 10.1016/S0012-365X(01)00312-0
M3 - 期刊論文
AN - SCOPUS:31244431634
SN - 0012-365X
VL - 247
SP - 235
EP - 242
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -