Algorithmic aspects of partial list colourings (Q2703027)

Let \(G=(V,E)\) be a graph with \(n\) vertices, chromatic number \(\chi (G)\) and list chromatic number \(\chi _{l}(G)\). Suppose each vertex of \(V(G)\) is assigned a list of \(t\) colours. \textit{A. O. Albertson, S. Grossman} and \textit{R. Haas} [Discrete Math. 214, No. 1-3, 235-240 (2000; Zbl 0957.05037)] conjectured that at least \(tn/\chi _{l}(G)\) vertices can be coloured properly from these lists. This paper presents algorithms that colour at least the number of vertices given in the bounds of Albertson, Grossman and Haas, and \textit{G. G. Chappell} [J. Graph Theory 32, No. 4, 390-393 (1999; Zbl 0939.05038)]. In particular, it follows that the conjecture is valid for all bipartite graphs and that, for every bipartite graph and every assignment of lists with \(t\) colours in each list where \(0\leq t\leq \chi _{l}(G)\), it is possible to colour at least \((1-(1/2)^{t})n\) vertices in polynomial time. Thus, if \(G\) is bipartite and \({\mathcal L}\) is a list assignment with \(|L(v)|\geq \text{ log}_{2}n\) for all \(v\in V\), then \(G\) is \({\mathcal L}\)-list colourable in polynomial time. The idea of proof relies on the method of conditional probabilities.