Acyclic, star and injective colouring: bounding the diameter

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

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. Acyclic, star and injective colouring: bounding the diameter

• Presentation Conference Type: Conference Paper (published)
• 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
• Print ISSN: 0302-9743
• 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