Skip to main content

Research Repository

Advanced Search

Colouring graphs of bounded diameter in the absence of small cycles

Martin, B.; Paulusma, D.; Smith, S.

Colouring graphs of bounded diameter in the absence of small cycles Thumbnail


Authors



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





You might also like



Downloadable Citations