Skip to main content

Research Repository

Advanced Search

Obtaining Online Ecological Colourings by Generalizing First-Fit

Johnson, M.; Patel, V.; Paulusma, D.; Trunck, T.

Obtaining Online Ecological Colourings by Generalizing First-Fit Thumbnail


Authors

M. Johnson

V. Patel

T. Trunck



Abstract

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 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, and to show that deciding whether (G,c) is ecologically extendible can be done in polynomial time. We also describe when the extension is possible using only colours from a given finite set C. 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 using the colours of c plus one extra colour. We also study (off-line) ecological H-colourings (an H-colouring of G is a homomorphism from G to H). We study the problem of deciding whether G has an ecological H-colouring for some fixed H and give a characterization of its computational complexity in terms of the structure of H.

Citation

Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2014). Obtaining Online Ecological Colourings by Generalizing First-Fit. Theory of Computing Systems, 54(2), 244-260. https://doi.org/10.1007/s00224-013-9513-9

Journal Article Type Article
Publication Date Feb 1, 2014
Deposit Date Dec 20, 2014
Publicly Available Date Mar 28, 2024
Journal Theory of Computing Systems
Print ISSN 1432-4350
Electronic ISSN 1433-0490
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 54
Issue 2
Pages 244-260
DOI https://doi.org/10.1007/s00224-013-9513-9
Keywords Graph colouring, Graph homomorphisms, Online algorithms.
Public URL https://durham-repository.worktribe.com/output/1447790

Files





You might also like



Downloadable Citations