CONSECUTIVE LIST COLOURING AND A NEW GRAPH INVARIANT
Robert J. Waters · Journal of the London Mathematical Society · 2006
We consider a variation of the list colouring problem in which the lists are required to be sets of consecutive integers, and the colours assigned to adjacent vertices must differ by at least a fixed integer s. We introduce and investigate a new parameter τ(G) of a graph G, called the consecutive choosability ratio and defined to be the ratio of the required list size to the separation s in the limit as s → ∞. We show that the above limit exists and that, for finite graphs G, τ(G) is rational and is a refinement of the chromatic number χ(G). We provide general bounds on τ(G), and determine its value for various classes of graphs including bipartite graphs, circuits, wheels and balanced complete multipartite graphs. Finally, we explore relationships between τ(G) and the circular chromatic number χc(G).