Given a (proper) vertex coloring \( f \) of a graph \( G \) , where \( f:V(G)\rightarrow \mathbb {N} \) , the difference edge labeling induced by \( f \) is a function \( h:E(G)\rightarrow \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 labeling \( h\) induced by \( f \) is a (proper) edge coloring of \( G \) . A graceful coloring with co-domain \( \{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)\le \chi _g(G)\le 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\ge 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. We show that graceful 4-colorability of chordal graphs is polynomial-time testable.

Graceful Coloring is Computationally Hard

会议论文
发表日期：

2025年

查看全文

Cyriac Antony,
Jacob Antony,
D. Laavanya,
S. Devi Yamini

摘要

Given a (proper) vertex coloring \( f \) of a graph \( G \) , where \( f:V(G)\rightarrow \mathbb {N} \) , the difference edge labeling induced by \( f \) is a function \( h:E(G)\rightarrow \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 labeling \( h\) induced by \( f \) is a (proper) edge coloring of \( G \) . A graceful coloring with co-domain \( \{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)\le \chi _g(G)\le 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\ge 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. We show that graceful 4-colorability of chordal graphs is polynomial-time testable.