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.