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



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 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. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026

Journal Article Type Article
Acceptance Date Feb 22, 2022
Online Publication Date Mar 19, 2022
Publication Date Jun 15, 2022
Deposit Date May 18, 2022
Publicly Available Date Mar 20, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 314
Pages 150-161
DOI https://doi.org/10.1016/j.dam.2022.02.026
Public URL https://durham-repository.worktribe.com/output/1206956

Files





You might also like



Downloadable Citations