Open neighbourhood colouring of some path related graphs

N. N. Swamy ; B. Sooryanarayana

Eurasian mathematical journal, Tome 6 (2015) no. 4, pp. 77-91

Résumé

An open neighbourhood $k$-colouring of a simple connected undirected graph $G(V,E)$ is a $k$-colouring $c : V\to \{1,2,\dots,k\}$, such that, for every $w \in V$ and for all $u,v \in N(w)$, $c(u) \ne c(v)$. The minimal value of $k$ for which $G$ admits an open neighbourhood $k$-colouring is called the open neighbourhood chromatic number of $G$ and is denoted by $\chi_{onc} (G)$. In this paper, we obtain the open neighbourhood chromatic number of the line graph and total graph of a path $P_n$. We also obtain the open neighbourhood chromatic number of two families of graphs which are derived from a path $P_n$, namely $k^{th}$ power of a path and transformation graph of a path.