Choosability and fractional chromatic numbers

N. Alon, Zs Tuza, M. Voigt

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

A graph G is (a,b)-choosable if for any assignment of a list of a colors to each of its vertices there is a subset of b colors of each list so that subsets corresponding to adjacent vertices are disjoint. It is shown that for every graph G, the minimum ratio a/b where a,b range over all pairs of integers for which G is (a,b)-choosable is equal to the fractional chromatic number of G.

Original languageEnglish (US)
Pages (from-to)31-38
Number of pages8
JournalDiscrete Mathematics
Volume165-166
DOIs
StatePublished - Mar 15 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Choosability and fractional chromatic numbers'. Together they form a unique fingerprint.

Cite this