On the fractional chromatic number, the chromatic number, and graph products

Sandi Klavžar, Hong Gwa Yeh

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)235-242
Number of pages8
JournalDiscrete Mathematics
Volume247
Issue number1-3
DOIs
StatePublished - 28 Mar 2002

Keywords

  • Chromatic number
  • Fractional chromatic number
  • Graph product
  • Uniquely colorable graph

Fingerprint

Dive into the research topics of 'On the fractional chromatic number, the chromatic number, and graph products'. Together they form a unique fingerprint.

Cite this