A Generalized Coloring of Graphs

Abstract

Let \(\chi^*(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]) \neq c(N_G[v])\) when \(N_G[u] \neq N_G[v]\) and \(c(u) \neq c(v)\) when \(N_G[u] = N_G[v]\). We show that the problem of deciding whether \(\chi^*(G) \leq n\), where \(n \geq 3\), is NP-complete for arbitrary graphs. We find \(\chi^*(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^*(G)\) in terms of \(\chi(G)\) and an upper bound is given for \(\chi^*(G)\) in terms of \(\Delta(G)\). For regular graphs with girth at least four, we give substantially better upper bounds for \(\chi^*(G)\) using random colorings of the
vertices.