Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Colouring graphs of bounded diameter in the absence of small cycles
Martin, B.; Paulusma, D.; Smith, S.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Siani Alice Smith siani.smith@durham.ac.uk
PGR Student Doctor of Philosophy
Contributors
Tiziana Calamoneri
Editor
Federico Corò
Editor
Abstract
For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two non-adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H-free if G does not contain any graph from H as an induced subgraph. Let Cs be the s-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of 3-Colouring for (C3, . . . , Cs)-free graphs and H-free graphs where H is some polyad. Here, we prove for certain small values of s that 3-Colouring is polynomial-time solvable for Cs-free graphs of diameter 2 and (C4, Cs)-free graphs of diameter 2. In fact, our results hold for the more general problem List 3-Colouring. We complement these results with some hardness result for diameter 4.
Citation
Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri, & F. Corò (Eds.), . https://doi.org/10.1007/978-3-030-75242-2_26
Conference Name | CIAC 2021 |
---|---|
Conference Location | Virtual Event |
Start Date | May 10, 2021 |
End Date | May 12, 2021 |
Acceptance Date | Dec 12, 2020 |
Online Publication Date | May 4, 2021 |
Publication Date | 2021 |
Deposit Date | Jan 16, 2021 |
Publicly Available Date | Jan 21, 2021 |
Publisher | Springer Verlag |
Pages | 367-380 |
Series Title | Lecture Notes in Computer Science |
Series ISSN | 0302-9743 |
ISBN | 978-3-030-75241-5 |
DOI | https://doi.org/10.1007/978-3-030-75242-2_26 |
Public URL | https://durham-repository.worktribe.com/output/1139803 |
Files
Accepted Conference Proceeding
(512 Kb)
PDF
Copyright Statement
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-75242-2_26
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