Choosability and fractional chromatic numbers. (English) Zbl 0877.05020

Let \(G=(V,E)\) be a graph. The problem of finding its chromatic number, \(\chi(G)\), can be formulated as an integer linear program: \[ \text{minimize}\quad \sum_{S\in{\mathcal S}(G)}\phi(S),\quad\text{over all }\phi\in{\mathcal P}(G); \]
\[ \text{subject to}\quad\sum_{\phi\in S\in{\mathcal S}(G)}\phi(S)\geq 1,\quad\text{for all }\nu\in V, \] where \({\mathcal S}(G)\) denotes the collection of all independent subsets of \(V\) and \({\mathcal P}(G)\) denotes the collection of all functions \(\phi:{\mathcal S}(G)\to \{0,1\}\). The minimum is \(\chi(G)\). If we replace \({\mathcal P}(G)\) by \({\mathcal R}(G)\), the collection of all functions \(\phi:{\mathcal S}(G)\to[0,1]\), the minimum is called the fractional chromatic number \(\chi^*(G)\).
Another variation of the chromatic number is the choice ratio of \(G\) and it is defined as follows. For integers \(a\) and \(b\) with \(a\geq 2b>1\), we say that \(G\) is \((a,b)\)-choosable if, for any assignment of lists of colors, \(L(\nu)\), to the vertices of \(G\) with \(|L(\nu)|=a\) (for all \(\nu\in V\)), there are sublists \(C(\nu)\subset L(\nu)\) with \(|C(\nu)|= b\) (for all \(\nu\in V\)) and \(C(\nu)\cap C(\omega)=\varnothing\), whenever \(\nu\) and \(\omega\) are adjacent. The choice ratio of \(G\) is then defined to be \(\inf\{{a\over b}\mid G\) is \((a,b)\)-choosable}.
The authors give several results relating these two extensions of the chromatic number; the easiest to state is Theorem 1.2: The choice ratio of any graph equals its fractional chromatic number.


05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C38 Paths and cycles
Full Text: DOI


[1] Alon, N., Restricted colorings of graphs, (), 1-33 · Zbl 0791.05034
[2] Alon, N.; Berman, K., Regular hypergraphs, Gordon’s lemma, Steinitz’s lemma and invariant theory, J. combin. theory ser. A, 43, 91-97, (1986) · Zbl 0611.05044
[3] Alon, N.; Kleitman, D.J.; Pomerance, C.; Saks, M.; Seymour, P., The smallest n-uniform hypergraph with positive discrepancy, Combinatorica, 7, 151-160, (1987) · Zbl 0629.05053
[4] Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, (), 125-157
[5] Graver, J.E., A survey of the maximum depth problem for indecomposable exact covers, (), 731-743 · Zbl 0306.05015
[6] Gutner, S., ()
[7] Tuza, Zs.; Voigt, M., On a conjecture of Erdös, (), 69-82 · Zbl 0864.05036
[8] Tuza, Zs.; Voigt, M., Every 2-choosable graph is (2m,m)-choosable, J. graph theory, 22, 245-252, (1996) · Zbl 0853.05034
[9] Vizing, V.G., Coloring the vertices of a graph in prescribed colors (in Russian), (), 3-10 · Zbl 1249.90303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.