Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-09T08:06:56.980Z Has data issue: false hasContentIssue false

CONSECUTIVE LIST COLOURING AND A NEW GRAPH INVARIANT

Published online by Cambridge University Press:  16 June 2006

R. J. WATERS
Affiliation:
School of Mathematical Sciences, University of Nottingham, University Park, Nottingham, NG7 2RD, United [email protected] Judge Business School, University of Cambridge, Trumpington Street, Cambridge, CB2 1AG, United Kingdom
Get access

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)$.

Keywords

Type
Notes and Papers
Copyright
The London Mathematical Society 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)