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