Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

Barnaby Martin; Daniël Paulusma; Siani Smith

doi:10.1007/978-3-030-75242-2_26

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

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

^*Corresponding author for this work

School of Mathematics

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

4 Citations (Scopus)

Abstract

For k≥ 1, a k-colouring c of G is a mapping from V(G) to { 1, 2, …, k} such that c(u) ≠ c(v) for any two non-adjacent vertices u and v. The k -Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H -free if G does not contain any graph from H as an induced subgraph. Let C_s be the s-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of 3-Colouring for (C₃, …, C_s) -free graphs and H-free graphs where H is some polyad. Here, we prove for certain small values of s that 3-Colouring is polynomial-time solvable for C_s -free graphs of diameter 2 and (C₄, C_s) -free graphs of diameter 2. In fact, our results hold for the more general problem List 3-Colouring. We complement these results with some hardness result for diameter 4.

Original language	English
Title of host publication	Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings
Editors	Tiziana Calamoneri, Federico Corò
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	367-380
Number of pages	14
ISBN (Print)	9783030752415
DOIs	https://doi.org/10.1007/978-3-030-75242-2_26
Publication status	Published - 4 May 2021
Event	12th International Conference on Algorithms and Complexity, CIAC 2021 - Virtual, Online Duration: 10 May 2021 → 12 May 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12701 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Algorithms and Complexity, CIAC 2021
City	Virtual, Online
Period	10/05/21 → 12/05/21

Bibliographical note

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

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-75242-2_26Licence: Unspecified

https://arxiv.org/abs/2101.07856

Handle.net

Persistent link

Cite this

Martin, B., Paulusma, D., & Smith, S. (2021). Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. In T. Calamoneri, & F. Corò (Eds.), Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings (pp. 367-380). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12701 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-75242-2_26

Martin, Barnaby ; Paulusma, Daniël ; Smith, Siani. / Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings. editor / Tiziana Calamoneri ; Federico Corò. Springer Science and Business Media Deutschland GmbH, 2021. pp. 367-380 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{88c05b55c3aa4d169279268ef6361c64,

title = "Colouring Graphs of Bounded Diameter in the Absence of Small Cycles",

abstract = "For k≥ 1, a k-colouring c of G is a mapping from V(G) to \{ 1, 2, …, k\} such that c(u) ≠ c(v) for any two non-adjacent vertices u and v. The k -Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H -free if G does not contain any graph from H as an induced subgraph. Let Cs be the s-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of 3-Colouring for (C3, …, Cs) -free graphs and H-free graphs where H is some polyad. Here, we prove for certain small values of s that 3-Colouring is polynomial-time solvable for Cs -free graphs of diameter 2 and (C4, Cs) -free graphs of diameter 2. In fact, our results hold for the more general problem List 3-Colouring. We complement these results with some hardness result for diameter 4.",

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

note = "Funding Information: Research supported by the Leverhulme Trust (RPG-2016-258). Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 12th International Conference on Algorithms and Complexity, CIAC 2021 ; Conference date: 10-05-2021 Through 12-05-2021",

year = "2021",

month = may,

day = "4",

doi = "10.1007/978-3-030-75242-2\_26",

language = "English",

isbn = "9783030752415",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "367--380",

editor = "Tiziana Calamoneri and Federico Cor{\`o}",

booktitle = "Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings",

address = "Germany",

}

Martin, B, Paulusma, D & Smith, S 2021, Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. in T Calamoneri & F Corò (eds), Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12701 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 367-380, 12th International Conference on Algorithms and Complexity, CIAC 2021, Virtual, Online, 10/05/21. https://doi.org/10.1007/978-3-030-75242-2_26

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. / Martin, Barnaby; Paulusma, Daniël; Smith, Siani.
Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings. ed. / Tiziana Calamoneri; Federico Corò. Springer Science and Business Media Deutschland GmbH, 2021. p. 367-380 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12701 LNCS).

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

TY - GEN

T1 - Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

PY - 2021/5/4

Y1 - 2021/5/4

N2 - For k≥ 1, a k-colouring c of G is a mapping from V(G) to { 1, 2, …, k} such that c(u) ≠ c(v) for any two non-adjacent vertices u and v. The k -Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H -free if G does not contain any graph from H as an induced subgraph. Let Cs be the s-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of 3-Colouring for (C3, …, Cs) -free graphs and H-free graphs where H is some polyad. Here, we prove for certain small values of s that 3-Colouring is polynomial-time solvable for Cs -free graphs of diameter 2 and (C4, Cs) -free graphs of diameter 2. In fact, our results hold for the more general problem List 3-Colouring. We complement these results with some hardness result for diameter 4.

AB - For k≥ 1, a k-colouring c of G is a mapping from V(G) to { 1, 2, …, k} such that c(u) ≠ c(v) for any two non-adjacent vertices u and v. The k -Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H -free if G does not contain any graph from H as an induced subgraph. Let Cs be the s-vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of 3-Colouring for (C3, …, Cs) -free graphs and H-free graphs where H is some polyad. Here, we prove for certain small values of s that 3-Colouring is polynomial-time solvable for Cs -free graphs of diameter 2 and (C4, Cs) -free graphs of diameter 2. In fact, our results hold for the more general problem List 3-Colouring. We complement these results with some hardness result for diameter 4.

UR - https://www.scopus.com/pages/publications/85106151234

U2 - 10.1007/978-3-030-75242-2_26

DO - 10.1007/978-3-030-75242-2_26

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85106151234

SN - 9783030752415

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 367

EP - 380

BT - Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings

A2 - Calamoneri, Tiziana

A2 - Corò, Federico

PB - Springer Science and Business Media Deutschland GmbH

T2 - 12th International Conference on Algorithms and Complexity, CIAC 2021

Y2 - 10 May 2021 through 12 May 2021

ER -

Martin B, Paulusma D, Smith S. Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. In Calamoneri T, Corò F, editors, Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 367-380. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-75242-2_26

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this