Skip to main content

Research Repository

Advanced Search

Acyclic, star and injective colouring: bounding the diameter

Brause, C.; Golovach, P.A.; Martin, B.; Paulusma, D.; Smith, S.

Acyclic, star and injective colouring: bounding the diameter Thumbnail


Authors

C. Brause

P.A. Golovach



Contributors

Łukasz Kowalik
Editor

Michał Pilipczuk
Editor

Paweł Rzążewski
Editor

Abstract

We examine the effect of bounding the diameter for wellstudied 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

Citation

Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Ł. Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (336-348). https://doi.org/10.1007/978-3-030-86838-3_26

Acceptance Date Apr 28, 2021
Online Publication Date Sep 20, 2021
Publication Date 2021
Deposit Date May 28, 2021
Publicly Available Date Aug 24, 2021
Publisher Springer Verlag
Volume 12911
Pages 336-348
Series Title Lecture Notes in Computer Science
Series ISSN 0302-9743
Edition 1
Book Title Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers
ISBN 9783030868376
DOI https://doi.org/10.1007/978-3-030-86838-3_26
Public URL https://durham-repository.worktribe.com/output/1653973

Files





You might also like



Downloadable Citations