Computation of lucky number of planar graphs is NP-hard

DOI10.1016/J.IPL.2011.11.002zbMATH Open1239.05161OpenAlexW2000213858MaRDI QIDQ413250FDOQ413250

Authors: A. Ahadi, A. Dehghan, M. Kazemi, E. Mollaahmadi 

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

Recommendations

• Lucky labelings of graphs
• On the lucky choice number of graphs
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Sigma partitioning: complexity and random graphs
• A lower bound and several exact results on the \(d\)-lucky number

zbMATH Keywords

computational complexitygraph coloringlucky labeling

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• On the additive chromatic number of several families of graphs
• Lucky labelings of graphs
• Topological additive numbering of directed acyclic graphs
• On the semi-proper orientations of graphs
• On strongly planar not-all-equal 3SAT
• Algorithmic complexity of proper labeling problems
• Additive list coloring of planar graphs with given girth
• A lower bound and several exact results on the \(d\)-lucky number
• Title not available (Why is that?)
• An Alon-Tarsi style theorem for additive colorings
• Algorithmic complexity of weakly semiregular partitioning and the representation number

This page was built for publication: Computation of lucky number of planar graphs is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q413250)