The computational complexity of cordial and equitable labelling

A labelling of a simple graph G = (V,E) is an assignment f of integers to the vertices of G. Under such a labelling f, we let V denote the set of vertices in G that are labelled i, and let E = {{u,?}: {u,?} ? E and |f(u) - f(?)| = j}. A k-equitable labelling of a graph G = (V,E) is a labelling f:V ? {0, 1,...,k - 1} such that, for each 0=i <j=k - 1, we have |V| -|V| ? {-1,0,1} and |E| - |E| ? {-1,0,1}. A cordial labelling of a graph G is a 2-equitable labelling of G. In this paper, we prove that the problem of deciding whether a graph G admits a cordial labelling is NP-complete, as conjectured by Kirchherr (Discrete Math. 115 (1993) 201-209). This implies that the problem of determining whether a graph G admits a k-equitable labelling is also NP-complete. A complexity result concerning another related type of labelling, known as k-cordial labelling, is also obtained.