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. (2021) 'Colouring graphs of bounded diameter in the absence of small cycles.', CIAC 2021.


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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:12 December 2020
Date deposited:21 January 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar