A Note on Graceful Graphs with Large Chromatic Numbers.
Ahmad Mahmoody · 2009
A graceful labeling of a graph G with m edges is a function f: V (G) ! f0; : : : ; mg such that distinct vertices receive distinct numbers and fjf(u) f(v)j: uv 2 E(G)g = f1; : : : ; mg. 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 6?". In this paper it is shown that for any natural number n, there exists a graceful graph G with (G) = n. For a graph G we denote the set of vertices and the set of edges of G with V (G) and E(G), respectively. The chromatic number of a graph G, denoted by (G) is the minimum number of independent subsets into which V (G) can be partitioned. A graceful labeling of a graph G with m edges is a function f: V (G) ! f0; : : :;mg such that distinct vertices receive distinct numbers and fjf(u)f(v)j: uv 2 E(G)g = f1; : : :;mg. A graph is graceful if it has a graceful labeling. The label of an edge is the dierence between