Skip to main content

Research Repository

Advanced Search

Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs

Huang, S.; Johnson, M.; Paulusma, D.

Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs Thumbnail


Authors

S. Huang

M. Johnson



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





You might also like



Downloadable Citations