GRACEFUL CHROMATIC NUMBER OF SOME CARTESIAN PRODUCT GRAPHS

Abstract

A graph G(V,E) is a system consisting of a finite non empty set of vertices V (G) and a set of edges E(G). A (proper) vertex colouring of G is a function f : V (G) →{1, 2,…,k}, for some positive integer k such that f(u)≠f(v) for every edge uv ∈ E(G). Moreover, if |f(u) - f(v)|≠|f(v) - f(w)| for every adjacent edges uv,vw ∈ E(G), then the function f is called graceful colouring for G. The minimum number k such that f is a graceful colouring for G is called the graceful chromatic number of G. The purpose of this research is to determine graceful chromatic number of Cartesian product graphs Cm×Pn for integers m ≥ 3 and n ≥ 2, and Cm × Cn for integers m,n ≥ 3. Here, Cm and Pm are cycle and path with m vertices, respectively. We found some exact values and bounds for graceful chromatic number of these mentioned Cartesian product graphs.