Premium
An Upper Bound for List T ‐Colourings
Author(s) -
Waller Adrian
Publication year - 1996
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms/28.4.337
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , degree (music) , upper and lower bounds , discrete mathematics , physics , acoustics , mathematical analysis
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.