Article ID Journal Published Year Pages File Type
4650986 Discrete Mathematics 2007 10 Pages PDF
Abstract
List 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).
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,