Sigma Partitioning: Complexity and Random Graphs

Abstract

A $\text{sigma partitioning}$ of a graph $G$ is a partition of the vertices into sets $P_1,\dots ,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 $\text{ sigma number}$ of a graph $G$, denoted by $\sigma (G)$, is the minimum number $k$ such that $G$ has a sigma partitioning $P_1,\dots ,P_k$. Also, a $\text{ lucky labeling}$ of a graph $G$ is a function $\ell :V(G)\to \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, ${\sum }_{w\sim v}\ell (w)\ne {\sum }_{w\sim u}\ell (w)$ ($x\sim y$ means that $x$ and $y$ are adjacent). The $\text{ lucky number}$ of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a lucky labeling $\ell :V(G)\to {\mathbb{N}}_k$. It was conjectured in [Inform. Process. Lett., 112(4):109--112, 2012] that it is $\mathbf{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.

References in corpus (4)

• The 1-2-3 Conjecture and related problems: a survey
• Algorithmic complexity of proper labeling problems
• A generalization of Combinatorial Nullstellensatz
• Additive colorings of planar graphs