Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter

Barnaby Martin; Daniël Paulusma; Siani Smith

doi:10.1016/j.tcs.2022.07.034

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter

Barnaby Martin, Daniël Paulusma^*, Siani Smith

^*Corresponding author for this work

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

Abstract

For a fixed integer, the k-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 for all k≥3, the k-COLOURING problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

Original language	English
Pages (from-to)	104-116
Number of pages	13
Journal	Theoretical Computer Science
Volume	931
DOIs	https://doi.org/10.1016/j.tcs.2022.07.034
Publication status	Published - 29 Sept 2022

Bibliographical note

Funding Information:
Supported by the Leverhulme Trust (RPG-2016-258).

Publisher Copyright:
© 2022 Elsevier B.V.

Keywords

Diameter
H-free graph
Vertex colouring

Access to Document

10.1016/j.tcs.2022.07.034

Handle.net

Persistent link

Cite this

@article{4ab4fbf8169e4f798d67a0e4491b80a4,

title = "Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter",

abstract = "For a fixed integer, the k-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 for all k≥3, the k-COLOURING problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.",

keywords = "Diameter, H-free graph, Vertex colouring",

author = "Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith",

note = "Funding Information: Supported by the Leverhulme Trust (RPG-2016-258). Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = sep,

day = "29",

doi = "10.1016/j.tcs.2022.07.034",

language = "English",

volume = "931",

pages = "104--116",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Amsterdam:Elsevier",

}

TY - JOUR

T1 - Colouring generalized claw-free graphs and graphs of large girth

T2 - Bounding the diameter

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

PY - 2022/9/29

Y1 - 2022/9/29

N2 - For a fixed integer, the k-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 for all k≥3, the k-COLOURING problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

AB - For a fixed integer, the k-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 for all k≥3, the k-COLOURING problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

KW - Diameter

KW - H-free graph

KW - Vertex colouring

UR - http://www.scopus.com/inward/record.url?scp=85137121266&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2022.07.034

DO - 10.1016/j.tcs.2022.07.034

M3 - Article (Academic Journal)

AN - SCOPUS:85137121266

SN - 0304-3975

VL - 931

SP - 104

EP - 116

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter

Abstract

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this