Choosability and fractional chromatic numbers (Q1356727): Difference between revisions

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.