The computational complexity of cordial and equitable labelling (Q1567263)

For a graph \(G=(V,E)\), a labelling \(f: V \rightarrow \{0,1,\ldots, k-1\}\) is \(k\)-equitable, if for each \(0 \leq i < j \leq k-1\), we have \(|V_i|- |V_j|\in \{-1,0,1\}\) and \(|E_i|- |E_j|\in \{-1,0,1\}\), where \(V_i\) is the set of vertices with label \(i\), and \(E_i\) is the set of edges \(\{v,w\}\) with \(|f(v) - f(w)|= i\). A 2-equitable labelling is called cordial, i.e., the vertices are partitioned into two sets of equal or almost equal size, such that (about) half of the edges are between vertices in different classes. It is shown that it is NP-complete to decide if a given graph has a cordial labelling; and hence it is also NP-complete to decide if a graph has a \(k\)-equitable labelling. As an intermediate result, the authors show that the problem, given a graph with an even number of edges, to decide if the vertices can be partitioned into two classes with exactly half of the edges from one class to the other is NP-complete.