An Upper Bound for List T -Colourings
Adrian O. Waller · Bulletin of the London Mathematical Society · 1996
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.