Bounds For Partial List Colourings.
Ruth Haas, Denis Hanson, Gary MacGillivray · 2003
Abstract: Let G be a simple graph on n vertices with list chromatic number χ l = s. If each vertex of G is assigned a list of t colours Albertson, Grossman and Haas [1] asked how many of the vertices, λ t,s, are necessarily colourable from these lists? They conjectured that λ t,s ≥ tn/s. Their work was extended by Chappell [2]. We improve the known lower bounds for λ t,s. Primary AMS subject classification: 05C15 §1. Introduction. Let G be a simple graph on n vertices. Suppose that each vertex x ∈ V(G) is assigned a list, l(x), of possible colours. A proper colouring c: V(G) → R is a list colouring of G if c(x) ∈ l(x) for all x ∈ V(G). The graph G is s-choosable if there exists a list colouring for every assignment of lists of s = |l(x) | colours.