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.
| Original language | English |
|---|---|
| Title of host publication | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 |
| Editors | Joost-Pieter Katoen, Pinar Heggernes, Peter Rossmanith |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (Electronic) | 9783959771177 |
| DOIs | |
| Publication status | Published - Aug 2019 |
| Event | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 - Aachen, Germany Duration: 26 Aug 2019 → 30 Aug 2019 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 138 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 |
|---|---|
| Country/Territory | Germany |
| City | Aachen |
| Period | 26/08/19 → 30/08/19 |
Bibliographical note
Funding Information:supported by the Leverhulme Trust (RPG-2016-258).
Publisher Copyright:
© Barnaby Martin, Daniël Paulusma, and Siani Smith.
Keywords
- Diameter
- H-free graph
- Vertex colouring