A Note on Graceful Graphs with Large Chromatic Numbers

Abstract

A graceful labeling of a graph \(G\) with \(m\) edges is a function \(f: V(G) \to \{0, \ldots, m\}\) such that distinct vertices receive distinct numbers and \(\{|f(u) – f(v)|: uv \in E(G)\} = \{1, \ldots, m\}\). A graph is graceful if it has a graceful labeling. In \([1]\) this question was posed: “Is there an \(n\)-chromatic graceful graph for \(n \geq 6\)?”. In this paper it is shown that for any natural number \(n\), there exists a graceful graph \(G\) with \(\chi(G) = n\).