Computation of lucky number of planar graphs is NP-hard

DOI10.1016/j.ipl.2011.11.002zbMath1239.05161OpenAlexW2000213858MaRDI QIDQ413250

J. Herrera, H. S. Yoon

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.11.002

zbMATH Keywords

computational complexitygraph coloringlucky labeling

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On strongly planar not-all-equal 3SAT, Additive list coloring of planar graphs with given girth, On the semi-proper orientations of graphs, Algorithmic complexity of proper labeling problems, Topological additive numbering of directed acyclic graphs, Algorithmic complexity of weakly semiregular partitioning and the representation number, Unnamed Item, A lower bound and several exact results on the \(d\)-lucky number, On the additive chromatic number of several families of graphs

Cites Work

• 1,2 conjecture-the multiplicative version
• Lucky labelings of graphs
• Some simplified NP-complete graph problems
• Edge weights and vertex colours
• Degree constrained subgraphs
• Vertex colouring edge partitions