An Upper Bound for List T ‐Colourings

Erdős, Rubin and Taylor showed in 1979 that for any connected graph G which is not a complete graph or an odd cycle, ch( G ) ⩽ Δ, where Δ is the maximum degree of a vertex in G and ch( G ) is the choice number of the graph (also proved by Vizing in 1976). They also gave a characterisation of D ‐choosability. A graph G is D ‐choosable if, when we assign to each vertex v of G a list containing d ( v ) elements, where d ( v ) is the degree of vertex v , we can always choose a proper vertex colouring from these lists, however the lists were chosen. In this paper we shall generalise their results on the choice number of G and D ‐choosability to the case where we have T ‐colourings.