We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Obtaining online ecological colourings by generalizing first-fit.

Johnson, M. and Patel, V. and Paulusma, Daniel and Trunck, T. (2010) 'Obtaining online ecological colourings by generalizing first-fit.', in Computer science : theory and applications : 5th International Computer Science Symposium in Russia, CSR, 16-20 June 2010, Kazan, Russia ; proceedings. Berlin ; Heidelberg: Springer, pp. 240-251. Lecture notes in computer science. (6072).


A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vertices added to G, one at a time, be coloured using colours from some finite set C so that at each stage the current graph is ecologically coloured? If the answer is yes, then we say that the pair (G,c) is ecologically online extendible. By generalizing the well-known First-Fit algorithm, we are able to characterize when (G,c) is ecologically online extendible. For the case where c is a colouring of G in which each vertex is coloured distinctly, we give a simple characterization of when (G,c) is ecologically online extendible using only the colours of c, and we also show that (G,c) is always online extendible if we permit ourselves to use one extra colour. We also study (off-line) ecological H-colourings where the colouring must satisfy further restrictions imposed by some fixed pattern graph H. We characterize the computational complexity of this problem. This solves an open question posed by Crescenzi et al.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Record Created:06 Oct 2010 12:05
Last Modified:31 Mar 2015 13:11

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library