Computation of lucky number of planar graphs is NP-hard

A lucky labeling of a graph G   is a function ℓ:V(G)→Nℓ:V(G)→N, such that for every two adjacent vertices v and u of G  , ∑w∼vℓ(w)≠∑w∼uℓ(w)∑w∼vℓ(w)≠∑w∼uℓ(w) (x∼yx∼y means that x is joined to y). A lucky number of G  , denoted by η(G)η(G), is the minimum number k such that G   has a lucky labeling ℓ:V(G)→{1,…,k}ℓ:V(G)→{1,…,k}. We prove that for a given planar 3-colorable graph G   determining whether η(G)=2η(G)=2 is NP-complete. Also for every k⩾2k⩾2, it is NP-complete to decide whether η(G)=kη(G)=k for a given graph G.

► We study the computational complexity of lucky number problems.
► We prove that, it is NP-complete to decide for a given planar 3-colorable graph G  , whether η(G)=2η(G)=2.
► We reduced 3-Colorability to problem LkLk for k⩾2k⩾2, in polynomial time.
► We concluded for every k⩾2k⩾2, it is NP-complete to decide whether η(G)=kη(G)=k for a given graph G.