Sigma Partitioning: Complexity and Random Graphs

A sigma partitioning of a graph C is a partition of the vertices into sets P-1, ..., P-k such that for every two adjacent vertices u and v there is an index i such that u and v have different numbers of neighbors in P-i. The sigma number of a graph G, denoted by sigma(G), is the minimum number k such that G has a sigma partitioning P-1, ..., P-k. Also, a lucky labeling of a graph G is a function l : V(G) -> N, such that for every two adjacent vertices v and u of G, Sigma(w similar to v)l(w) not equal Sigma(w similar to u) l(w) (x similar to y means that x and y are adjacent). The lucky number of G. denoted by eta(G), is the minimum number k such that G has a lucky labeling l : V(G) -> N-k. It was conjectured in [Inform. Process. Lett., 112(4):109-112, 2012] that it is NP-complete to decide whether eta(G) = 2 for a given 3-regular graph G. In this work, we prove this conjecture. Among other results, we give an upper bound of five for the sigma number of a uniformly random graph.