List Set Colouring: Bounds and Algorithms
Charumathi Raghu Subramanian · Combinatorics Probability Computing · 2006
For an integer $b \geq 1$ , the $b$ -choice number of a graph $G$ is the minimum integer $k$ such that, for every assignment of a set $S(v)$ of at least $k$ colours to each vertex $v$ of $G$ , there is a $b$ -set colouring of $G$ that assigns to each vertex $v$ a $b$ -set $B(v) \subseteq S(v) \; (|B(v)|=b)$ so that adjacent vertices receive disjoint $b$ -sets. This is a generalization of the notions of choice number and chromatic number of a graph. Using probabilistic arguments, we show that, for some positive constant $c > 0$ (independent of $b$ ), the $b$ -choice number of any graph $G$ on $n$ vertices is at most $c (b\chi) (\ln (n/\chi)+1)$ where $\chi = \chi(G)$ denotes the chromatic number of $G$ . For any fixed $b$ , this bound is tight up to a constant factor for each $n,\chi$ . This generalizes and extends a result of Noga Alon [1]wherein a similar bound was obtained for 1-choice numbers of complete $\chi$ -partite graphs with each part having size $n/\chi$ . We also show that the proof arguments are constructive, leading to polynomial time algorithms for the list colouring problem on certain classes of graphs, provided each vertex is given a list of sufficiently large size.