S. Huang
Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs
Huang, S.; Johnson, M.; Paulusma, D.
Authors
Contributors
Qianping Gu
Editor
Pavol Hell
Editor
Boting Yang
Editor
Abstract
Let k be a positive integer. The k-Colouring problem is to decide whether a graph has a k-colouring. The k-Precolouring Extension problem is to decide whether a colouring of a subset of a graph’s vertex set can be extended to a k-colouring of the whole graph. 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 asks whether the graph has a k-colouring in which each vertex is coloured with a colour from its list. We prove a number of new complexity results for 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).
Citation
Huang, S., Johnson, M., & Paulusma, D. (2014). Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs. In Q. Gu, P. Hell, & B. Yang (Eds.), 10th International Conference, AAIM 2014, Vancouver, BC, Canada, 8-11 July 2014 ; proceedings (162-173). https://doi.org/10.1007/978-3-319-07956-1_15
Conference Name | 10th International Conference, AAIM 2014 |
---|---|
Conference Location | Vancouver, BC, Canada |
Publication Date | Jan 1, 2014 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Mar 28, 2024 |
Pages | 162-173 |
Series Title | Lecture notes in computer science |
Series Number | 8546 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | 10th International Conference, AAIM 2014, Vancouver, BC, Canada, 8-11 July 2014 ; proceedings. |
ISBN | 978-3-319-07955-4 |
DOI | https://doi.org/10.1007/978-3-319-07956-1_15 |
Public URL | https://durham-repository.worktribe.com/output/1154476 |
Files
Accepted Conference Proceeding
(328 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-07956-1_15
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
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