Abstrakt
For a multi-set λ={k_1,k_2,...,k_q} of positive integers, let k_λ be the sum of all k_i. A λ-list assignment of G is a list assignment L of G such that the colour set N-ARY UNION_{vELEMENT OFV(G)}L(v) can be partitioned into the disjoint union C1_UNIONC_2UNION...UNIONC_q of q sets so that for each i and each vertex v of G, |L(v)INTERSECTIONC_i|>=k_i.
We say G is λ-choosable if G is L-colourable for any λ-list assignment L of G. The concept of λ-choosability puts k-colourability and k-choosability in the same framework: If λ={k}, then λ-choosability is equivalent to k-choosability; if λ consists of k copies of 1, then λ-choosability is equivalent to k-colourability. If G is λ-choosable, then G is k_λ-colourable. On the other hand, there are k_λ-colourable graphs that are not λ-choosable, provided that λ contains an integer larger than 1.
Let φ(λ) be the minimum number of vertices in a k_λ-colourable non-λ-choosable graph. This paper determines the value of φ(λ) for all λ.