A PROCEDURE FOR DERIVING ODD-GRACEFUL CHROMATIC NUMBERS OF GRAPHS

Abstract

 Let \(G:=(V,E)\) be an undirected finite simple graph with vertex set \(V\) and edge set \(E\). A function \(c:V(G)\rightarrow \{1,2,\ldots,k\},\) for some positive integer \(k\), such that \(c(u)\neq c(v)\) for every edge \(uv\in E(G)\), is called a (proper) vertex \(k\)-colouring of \(G\). If \(|c(u)-c(v)|\neq |c(v)-c(w)|\) for all adjacent edges \(uv,vw\in E(G)\), then the function \(c\) is called graceful colouring for \(G\). The smallest \(k\) which keeps \(c\) as graceful colouring is called the graceful chromatic number of \(G\). If in addition we have also that \(|c(u)-c(v)|\) is odd for every edge \(uv\in E\), then \(c\) is said to be odd-graceful colouring for \(G\), and the smallest \(k\) is called odd-graceful chromatic number of \(G\). We introduced a procedure to determine eligible colours for odd-graceful colouring of graph. By using this procedure, we derived odd-graceful chromatic numbers of some classes of star related-graphs which are built using vertex amalgamation or graphs combination.