Acyclic, Star, and Injective Colouring: Bounding the Diameter

Christoph Brause; Petr Golovach; Barnaby Martin; Daniël Paulusma; Siani Smith

doi:10.1007/978-3-030-86838-3_26

Acyclic, Star, and Injective Colouring: Bounding the Diameter

Christoph Brause
, Petr Golovach
, 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)

3 Citations (Scopus)

Abstract

We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as L (1, 1)-Labelling and we also consider the framework of L (a, b)-Labelling. We prove a number of (almost-)complete complexity classifications, in particular, for Acyclic 3-Colouring, Star 3-Colouring and L (1, 2)-Labelling.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers
Editors	Lukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	336-348
Number of pages	13
ISBN (Print)	9783030868376
DOIs	https://doi.org/10.1007/978-3-030-86838-3_26
Publication status	Published - 20 Sept 2021
Event	47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online Duration: 23 Jun 2021 → 25 Jun 2021

Publication series

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

Conference

Conference	47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
City	Virtual, Online
Period	23/06/21 → 25/06/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-86838-3_26Licence: Unspecified

https://arxiv.org/abs/2104.10593#:~:text=We%20examine%20the%20effect%20of%20bounding%20the%20diameter,or%20disjoint%20union%20of%20vertices%20and%20edges%2C%20respectively.

Handle.net

Persistent link

Cite this

Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, Star, and Injective Colouring: Bounding the Diameter. In L. Kowalik, M. Pilipczuk, & P. Rzazewski (Eds.), Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers (pp. 336-348). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12911 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-86838-3_26

Brause, Christoph ; Golovach, Petr ; Martin, Barnaby et al. / Acyclic, Star, and Injective Colouring : Bounding the Diameter. Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers. editor / Lukasz Kowalik ; Michal Pilipczuk ; Pawel Rzazewski. Springer Science and Business Media Deutschland GmbH, 2021. pp. 336-348 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9267f241dfac4fb695de77a8380e9939,

title = "Acyclic, Star, and Injective Colouring: Bounding the Diameter",

abstract = "We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as L (1, 1)-Labelling and we also consider the framework of L (a, b)-Labelling. We prove a number of (almost-)complete complexity classifications, in particular, for Acyclic 3-Colouring, Star 3-Colouring and L (1, 2)-Labelling.",

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

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 ; Conference date: 23-06-2021 Through 25-06-2021",

year = "2021",

month = sep,

day = "20",

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

language = "English",

isbn = "9783030868376",

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 = "336--348",

editor = "Lukasz Kowalik and Michal Pilipczuk and Pawel Rzazewski",

booktitle = "Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers",

address = "Germany",

}

Brause, C, Golovach, P, Martin, B, Paulusma, D & Smith, S 2021, Acyclic, Star, and Injective Colouring: Bounding the Diameter. in L Kowalik, M Pilipczuk & P Rzazewski (eds), Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12911 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 336-348, 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021, Virtual, Online, 23/06/21. https://doi.org/10.1007/978-3-030-86838-3_26

Acyclic, Star, and Injective Colouring: Bounding the Diameter. / Brause, Christoph; Golovach, Petr; Martin, Barnaby et al.
Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers. ed. / Lukasz Kowalik; Michal Pilipczuk; Pawel Rzazewski. Springer Science and Business Media Deutschland GmbH, 2021. p. 336-348 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12911 LNCS).

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

TY - GEN

T1 - Acyclic, Star, and Injective Colouring

T2 - 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021

AU - Brause, Christoph

AU - Golovach, Petr

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

PY - 2021/9/20

Y1 - 2021/9/20

N2 - We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as L (1, 1)-Labelling and we also consider the framework of L (a, b)-Labelling. We prove a number of (almost-)complete complexity classifications, in particular, for Acyclic 3-Colouring, Star 3-Colouring and L (1, 2)-Labelling.

AB - We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as L (1, 1)-Labelling and we also consider the framework of L (a, b)-Labelling. We prove a number of (almost-)complete complexity classifications, in particular, for Acyclic 3-Colouring, Star 3-Colouring and L (1, 2)-Labelling.

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

UR - https://wg2021.mimuw.edu.pl/

U2 - 10.1007/978-3-030-86838-3_26

DO - 10.1007/978-3-030-86838-3_26

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85115845344

SN - 9783030868376

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

SP - 336

EP - 348

BT - Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers

A2 - Kowalik, Lukasz

A2 - Pilipczuk, Michal

A2 - Rzazewski, Pawel

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 23 June 2021 through 25 June 2021

ER -

Brause C, Golovach P, Martin B, Paulusma D, Smith S. Acyclic, Star, and Injective Colouring: Bounding the Diameter. In Kowalik L, Pilipczuk M, Rzazewski P, editors, Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2021. p. 336-348. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-86838-3_26

Acyclic, Star, and Injective Colouring: Bounding the Diameter

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this