The Graceful Chromatic Number for Some Particular Classes of Graphs

Abstract

Graph colorings are a major area of study in graph theory involving the constrained assignment of labels (colors) to vertices or edges. There are many types of colorings defined in the literature. The most common type of coloring is the proper vertex k-coloring which is defined as a vertex coloring from a set of k colors such that no two adjacent vertices share a common color. Our central focus in this paper is a variant of the proper vertex k-coloring problem, termed graceful coloring introduced by Gary Chartrand in 2015. A graceful k-coloring of an undirected connected graph G is a proper vertex coloring using k colors that induces a proper edge coloring, where the color for an edge (u,v) is the absolute value of the difference between the colors assigned to vertices u and v. In this work we find the graceful chromatic number, the minimum k for which a graph has a graceful k-coloring, for some well-known graphs and classes of graphs, such as diamond graph, Petersen graph, Moser spindle graph, Goldner-Harary graph, friendship graphs, fan graphs and others.