Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Colouring H-free graphs of bounded diameter
Martin, B.; Paulusma, D.; Smith, S.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
S. Smith
Contributors
Peter Rossmanith
Editor
Pinar Heggernes
Editor
Joost-Pieter Katoen
Editor
Abstract
The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that Colouring is NP-complete for H-free graphs if H contains a cycle or claw, even for fixed k ≥3. We examine to what extent the situation may change if in addition the input graph has bounded diameter.
Citation
Martin, B., Paulusma, D., & Smith, S. (2019). Colouring H-free graphs of bounded diameter. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (14:1-14:14). https://doi.org/10.4230/lipics.mfcs.2019.14
Conference Name | MFCS 2019 |
---|---|
Conference Location | Aachen, Germany |
Start Date | Aug 26, 2019 |
End Date | Aug 30, 2019 |
Acceptance Date | Jun 11, 2019 |
Online Publication Date | Aug 20, 2019 |
Publication Date | Aug 31, 2019 |
Deposit Date | Jun 12, 2019 |
Publicly Available Date | Jul 2, 2019 |
Volume | 138 |
Pages | 14:1-14:14 |
Series Title | Leibniz international proceedings in informatics |
Series ISSN | 1868-8969 |
Book Title | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). |
DOI | https://doi.org/10.4230/lipics.mfcs.2019.14 |
Public URL | https://durham-repository.worktribe.com/output/1144026 |
Files
Accepted Conference Proceeding
(582 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Barnaby Martin, Daniel Paulusma and Siani Smith;
licensed under Creative Commons License CC-BY.
Published Conference Proceeding
(520 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
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