On the Local Colorings of Graphs

Abstract

A local coloring of a graph $G$ is a function $c:V(G)\to \mathbb{N}$ having the property that for each set $S\subseteq V(G)$ with $2\le |S|\le 3$, there exist vertices $u,v\in S$ such that $|c(u)–c(v)|\ge m_S$, where $m_S$ is the size of the induced subgraph $⟨S⟩$. The maximum color assigned by a local coloring $c$ to a vertex of $G$ is called the value of $c$ and is denoted by ${\chi }_{\ell }(c)$. The local chromatic number of $G$ is ${\chi }_{\ell }(G)=min\{{\chi }_{\ell }(c)\}$, where the minimum is taken over all local colorings $c$ of $G$. If ${\chi }_{\ell }(c)={\chi }_{\ell }(G)$, then $c$ is called a minimum local coloring of $G$. The local coloring of graphs introduced by Chartrand et al. in $2003$. In this paper, following the study of this concept, first an upper bound for ${\chi }_{\ell }(G)$ where $G$ is not complete graphs $K_4$ and $K_5$, is provided in terms of maximum degree $\mathrm{\Delta }(G)$. Then the exact value of ${\chi }_{\ell }(G)$ for some special graphs $G$ such as the cartesian product of cycles, paths and complete graphs is determined.