2024/07/02 by Cyriac Antony, Antony, Cyriac, D. Laavanya +3
Computer Science · Physics and Astronomy · #Color Science and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Image Retrieval and Classification Techniques
paper · pdf · doi:10.48550/arxiv.2407.02179
openalex publication_date 2024/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a (proper) vertex coloring f of a graph G, say f\colon V(G)→ ℕ, the difference edge labelling induced by f is a function h\colon E(G)→ ℕ 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 χ(G2)≤ χg(G)≤ a(χ(G2)) 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.