Skip to main content

Research Repository

Advanced Search

Colouring H-free graphs of bounded diameter

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

Colouring H-free graphs of bounded diameter Thumbnail


Authors

S. Smith



Contributors

Peter Rossmanith
Editor

Pinar Heggernes
Editor

Joost-Pieter Katoen
Editor

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). Colouring H-free graphs of bounded diameter. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (14:1-14:14). https://doi.org/10.4230/lipics.mfcs.2019.14

Conference Name MFCS 2019
Conference Location Aachen, Germany
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 Mar 29, 2024
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

Files






You might also like



Downloadable Citations