We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Colouring graphs of bounded diameter in the absence of small cycles

Martin, B. and Paulusma, D. and Smith, S. (2022) 'Colouring graphs of bounded diameter in the absence of small cycles.', Discrete applied mathematics., 314 . pp. 150-161.


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.

Item Type:Article
Full text:Publisher-imposed embargo until 19 March 2024.
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF
Publisher Web site:
Publisher statement:© 2022. This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:22 February 2022
Date deposited:19 May 2022
Date of first online publication:19 March 2022
Date first made open access:19 March 2024

Save or Share this output

Look up in GoogleScholar