Computation of lucky number of planar graphs is NP-hard

DOI10.1016/J.IPL.2011.11.002MaRDI QIDQ413250zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(15)

• On the additive chromatic number of several families of graphs
• Lucky labelings of graphs
• Sigma partitioning: complexity and random graphs
• Topological additive numbering of directed acyclic graphs
• On the lucky choice number of graphs
• On strongly planar not-all-equal 3SAT
• On the semi-proper orientations of graphs
• Algorithmic complexity of proper labeling problems
• \(e\)-lucky labeling of certain graphs
• Additive list coloring of planar graphs with given girth
• A lower bound and several exact results on the \(d\)-lucky number
• Heuristic method to determine lucky \(k\)-polynomials for \(k\)-colorable graphs
• scientific article; zbMATH DE number 7527894 (Why is no real title available?)
• 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)