Some new bounds on Tr-choosability

AbstractList T-colouring is a generalisation of list colouring in which the differences between adjacent colours must not lie in the set T. We present a conjecture giving an upper bound on the Tr-choosability Tr-ch(G) (where Tr={0,1,…,r}) in terms of r and ch(G) which, if true, is tight for all values of r and ch(G), and we prove the bound in the case ch(G)=2. We also prove the conjecture with the colouring number col(G) in place of ch(G), and use this result in conjunction with a theorem of Alon to establish an exponential upper bound on Tr-ch(G) in terms of r and ch(G)