Graceful coloring is computationally hard

Given a (proper) vertex coloring f of a graph G, say f V(G)→ N, the difference edge labelling induced by f is a function h E(G)→ N defined as $h(uv)=|f(u)-f(v)|$ for every edge $uv$ of G. A graceful coloring of G is a vertex coloring f of G such that the difference edge labelling h induced by f is a (proper) edge coloring of G. A graceful coloring with range \1,2,,k\ is called a graceful k-coloring. The least integer k such that G admits a graceful k-coloring is called the graceful chromatic number of G, denoted by χg(G). We prove that χ(G²)≤ χg(G)≤ a(χ(G²)) for every graph G, where $a(n)$ denotes the nth term of the integer sequence A065825 in OEIS. We also prove that graceful coloring problem is NP-hard for planar bipartite graphs, regular graphs and 2-degenerate graphs. In particular, we show that for each k≥ 5, it is NP-complete to check whether a planar bipartite graph of maximum degree $k-2$ is graceful k-colorable. The complexity of checking whether a planar graph is graceful 4-colorable remains open.