Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter

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

Abstract

For a fixed integer, the k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that for all k ≥ 3, the k-Colouring problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

Citation

Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034

• Journal Article Type: Article
• Acceptance Date: Jul 27, 2022
• Online Publication Date: Aug 2, 2022
• Publication Date: Sep 29, 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Aug 3, 2023
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 931
• Pages: 104-116
• DOI: https://doi.org/10.1016/j.tcs.2022.07.034
• Public URL: https://durham-repository.worktribe.com/output/1188689