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
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution. Download PDF (569Kb) |
| Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (508Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.4230/LIPIcs.MFCS.2019.14 |
| 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
| Export: | |
| Look up in GoogleScholar |
