Title of article
On the fractional chromatic number, the chromatic number, and graph products
Author/Authors
Sandi Klavzar، نويسنده , , Hong-Gwa Yeh، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2002
Pages
8
From page
235
To page
242
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
Serial Year
2002
Journal title
Discrete Mathematics
Record number
950014
Link To Document