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 H-free graphs of bounded diameter.

Martin, B. and Paulusma, D. and Smith, S. (2019) 'Colouring H-free graphs of bounded diameter.', in 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 14:1-14:14. Leibniz international proceedings in informatics., 138


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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© Barnaby Martin, Daniel Paulusma and Siani Smith; licensed under Creative Commons License CC-BY.
Date accepted:11 June 2019
Date deposited:02 July 2019
Date of first online publication:20 August 2019
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar