Algorithmic complexity of weakly semiregular partitioning and the representation number

In the second part of the work, we consider the representation number. A graph G has a representation modulo r if there exists an injective map ℓ:V(G)→Zr such that vertices v and u are adjacent if and only if |ℓ(u)−ℓ(v)| is relatively prime to r. The representation number, denoted by rep(G), is the smallest r such that G has a representation modulo r. Narayan and Urick conjectured that the determination of rep(G) for an arbitrary graph G is a difficult problem [38]. In this work, we confirm this conjecture and show that if NP≠P, then for any ϵ>0, there is no polynomial time (1−ϵ)n2-approximation algorithm for the computation of representation number of regular graphs with n vertices.