We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Obtaining Online Ecological Colourings by Generalizing First-Fit.
- Authors
Johnson, Matthew; Patel, Viresh; Paulusma, Daniël; Trunck, Théophile
- 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.
- Subjects
GRAPH coloring; ALGORITHMS; SET theory; HOMOMORPHISMS; COMPUTATIONAL complexity; MATHEMATICAL analysis
- Publication
Theory of Computing Systems, 2014, Vol 54, Issue 2, p244
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-013-9513-9