Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Obtaining online ecological colourings by generalizing first-fit
Johnson, M.; Patel, V.; Paulusma, D.; Trunck, T.
Authors
V. Patel
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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 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.
Citation
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. . https://doi.org/10.1007/978-3-642-13182-0_22
Conference Name | 5th International Computer Science Symposium in Russia (CSR 2010) |
---|---|
Publication Date | 2010 |
Deposit Date | Sep 30, 2010 |
Publisher | Springer Verlag |
Volume | 6072 |
Pages | 240-251 |
DOI | https://doi.org/10.1007/978-3-642-13182-0_22 |
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search