The complexity of \(L(p, q)\)-edge-labelling

DOI10.1007/s00453-023-01120-4MaRDI QIDQ6090539

Siani Smith, Gaétan Berthe, Daniël Paulusma, Barnaby Martin

Publication date: 17 November 2023

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

computational complexitycolouringNP-harddichotomy\(L(p, q)\)-labeling

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree
• On the computational complexity of strong edge coloring
• Computational complexity of distance edge labeling
• On the injective chromatic number of graphs
• Injective colouring for H-free graphs
• The complexity of \(L(p, q)\)-edge-labelling
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• The NP-Completeness of Edge-Coloring
• Labelling Graphs with a Condition at Distance 2
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• The complexity of satisfiability problems
• Acyclic, star, and injective colouring: bounding the diameter
• Fixed-parameter complexity of \(\lambda\)-labelings