Choosability and fractional chromatic numbers

N. Alon; Zs Tuza; M. Voigt

doi:10.1016/S0012-365X(96)00159-8

Choosability and fractional chromatic numbers

N. Alon
, Zs Tuza
, M. Voigt

Research output: Contribution to journal › Article › peer-review

38 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 language	English (US)
Pages (from-to)	31-38
Number of pages	8
Journal	Discrete Mathematics
Volume	165-166
DOIs	https://doi.org/10.1016/S0012-365X(96)00159-8
State	Published - Mar 15 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(96)00159-8

Cite this

@article{ab893cccab1a48fea36eecdb47cfb19b,

title = "Choosability and fractional chromatic numbers",

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.",

author = "N. Alon and Zs Tuza and M. Voigt",

note = "Funding Information: *Corresponding author. E-mail: [email protected]. {\textquoteright} Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences. * Research supported in part by the National Scientific Research Fund, grants 7558 and T016416.",

year = "1997",

month = mar,

day = "15",

doi = "10.1016/S0012-365X(96)00159-8",

language = "English (US)",

volume = "165-166",

pages = "31--38",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Choosability and fractional chromatic numbers

AU - Alon, N.

AU - Tuza, Zs

AU - Voigt, M.

N1 - Funding Information: *Corresponding author. E-mail: [email protected]. ’ Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences. * Research supported in part by the National Scientific Research Fund, grants 7558 and T016416.

PY - 1997/3/15

Y1 - 1997/3/15

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0002443622

UR - https://www.scopus.com/pages/publications/0002443622#tab=citedBy

U2 - 10.1016/S0012-365X(96)00159-8

DO - 10.1016/S0012-365X(96)00159-8

M3 - Article

AN - SCOPUS:0002443622

SN - 0012-365X

VL - 165-166

SP - 31

EP - 38

JO - Discrete Mathematics

JF - Discrete Mathematics

ER -

Choosability and fractional chromatic numbers

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this