Graceful coloring is computationally hard
<|reference_start|>Graceful coloring is computationally hard: Given a (proper) vertex coloring $f$ of a graph $G$, say $f\colon V(G)\to \mathbb{N}$, the difference edge labelling induced by $f$ is a function $h\colon E(G)\to \mathbb{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,\dots,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 $\chi_g(G)$.   We prove that $\chi(G^2)\leq \chi_g(G)\leq a(\chi(G^2))$ for every graph $G$, where $a(n)$ denotes the $n$th 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\geq 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.<|reference_end|>
@article{antony2024graceful,
    title={Graceful coloring is computationally hard},
    author={Cyriac Antony, Laavanya D. and Devi Yamini S},
    journal={arXiv preprint arXiv:2407.02179},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.02179},
    primaryClass={math.CO cs.DM}
}