A Generalized Coloring of Graphs

Abstract

Let ${\chi }^{\ast }(G)$ denote the minimum number of colors required in a coloring $c$ of the vertices of $G$ where for adjacent vertices $u,v$ we have $c(N_G[u])\ne c(N_G[v])$ when $N_G[u]\ne N_G[v]$ and $c(u)\ne c(v)$ when $N_G[u]=N_G[v]$. We show that the problem of deciding whether ${\chi }^{\ast }(G)\le n$, where $n\ge 3$, is NP-complete for arbitrary graphs. We find ${\chi }^{\ast }(G)$ for several classes of graphs, including bipartite graphs, complete multipartite graphs, as well as cycles and their complements. A sharp lower bound is given for ${\chi }^{\ast }(G)$ in terms of $\chi (G)$ and an upper bound is given for ${\chi }^{\ast }(G)$ in terms of $\mathrm{\Delta }(G)$. For regular graphs with girth at least four, we give substantially better upper bounds for ${\chi }^{\ast }(G)$ using random colorings of the
vertices.