Title of article :
On the fractional chromatic number, the chromatic number, and graph products
Author/Authors :
Sandi Klavzar، نويسنده , , Hong-Gwa Yeh، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2002
Abstract :
It is shown that the difference between the chromatic number χ and the fractional chromatic number χf can be arbitrarily large in the class of uniquely colorable, vertex transitive graphs. For the lexicographic product G∘H it is shown that χ(G∘H)⩾χ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 Bollobás and Thomason (for uniquely colorable graphs) are also proved in a simple, elementary way.
Keywords :
Chromatic number , Fractional chromatic number , Graph product , Uniquely colorable graph
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics