Colouring H-free graphs of bounded diameter

Barnaby Martin, Daniël Paulusma, Siani Smith

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

15 Citations (Scopus)

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 languageEnglish
Title of host publication44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
EditorsJoost-Pieter Katoen, Pinar Heggernes, Peter Rossmanith
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771177
DOIs
Publication statusPublished - Aug 2019
Event44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 - Aachen, Germany
Duration: 26 Aug 201930 Aug 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume138
ISSN (Print)1868-8969

Conference

Conference44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
Country/TerritoryGermany
CityAachen
Period26/08/1930/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

Fingerprint

Dive into the research topics of 'Colouring H-free graphs of bounded diameter'. Together they form a unique fingerprint.

Cite this