S. Huang
Narrowing the complexity gap for colouring (Cs, Pt)-free graphs
Huang, S.; Johnson, M.; Paulusma, D.
Authors
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Abstract
For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem is to decide, for a given G=(V,E), whether a colouring of a subset of V can be extended to a k-colouring of G. A k-list assignment of a graph is an allocation of a list—a subset of {1,…,k}—to each vertex, and the List k-Colouring problem is to decide, for a given G, whether G has a k-colouring in which each vertex is coloured with a colour from its list. We consider the computational complexity of these three decision problems when restricted to graphs that do not contain a cycle on s vertices or a path on t vertices as induced subgraphs (for fixed positive integers s and t). We report on past work and prove a number of new NP-completeness results.
Citation
Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039
Journal Article Type | Article |
---|---|
Acceptance Date | Apr 30, 2015 |
Publication Date | Nov 1, 2015 |
Deposit Date | Oct 31, 2015 |
Publicly Available Date | Jun 8, 2016 |
Journal | The Computer Journal |
Print ISSN | 0010-4620 |
Electronic ISSN | 1460-2067 |
Publisher | BCS, The Chartered Institute for IT |
Peer Reviewed | Peer Reviewed |
Volume | 58 |
Issue | 11 |
Pages | 3074-3088 |
DOI | https://doi.org/10.1093/comjnl/bxv039 |
Keywords | Graph colouring, Forbidden induced subgraph, Computational complexity, List colouring, Precolouring extension. |
Files
Accepted Journal Article
(230 Kb)
PDF
Copyright Statement
This is a pre-copyedited, author-produced PDF of an article accepted for publication in The Computer Journal following peer review. The version of record Huang, S., Johnson, Matthew and Paulusma, Daniel (2015) 'Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.', The computer journal., 58 (11): 3074-3088 is available online at: http://dx.doi.org/10.1093/comjnl/bxv039.
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