Colouring H-free graphs of bounded diameter

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

Abstract

The 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 Colouring is NP-complete for H-free graphs if H contains a cycle or claw, even for fixed k ≥3. 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. (2019, August). Colouring H-free graphs of bounded diameter. Presented at MFCS 2019, Aachen, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: MFCS 2019
• Start Date: Aug 26, 2019
• End Date: Aug 30, 2019
• Acceptance Date: Jun 11, 2019
• Online Publication Date: Aug 20, 2019
• Publication Date: Aug 31, 2019
• Deposit Date: Jun 12, 2019
• Publicly Available Date: Jul 2, 2019
• Volume: 138
• Pages: 14:1-14:14
• Series Title: Leibniz international proceedings in informatics
• Series ISSN: 1868-8969
• Book Title: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019).
• DOI: https://doi.org/10.4230/lipics.mfcs.2019.14
• Public URL: https://durham-repository.worktribe.com/output/1144026