On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs

DOI10.1016/j.tcs.2022.10.017zbMath1506.68065OpenAlexW4285685345MaRDI QIDQ2098173

Julien Bensmail, Dimitri Lajou, Hervé Hocquard

Publication date: 17 November 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.10.017

zbMATH Keywords

chromatic indexNP-hardnessadjacent vertex distinguishing graph coloringneighbour sum distinguishing graph coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Neighbor sum distinguishing index
• Adjacent strong edge coloring of graphs
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs

This page was built for publication: On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs