CONSECUTIVE LIST COLOURING AND A NEW GRAPH INVARIANT

Abstract

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 $\tau(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\to\infty$.

We show that the above limit exists and that, for finite graphs $G,\ \tau(G)$ is rational and is a refinement of the chromatic number $\chi(G)$. We provide general bounds on $\tau(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 $\tau(G)$ and the circular chromatic number $\chi_{\mathrm{c}}(G)$.