Abstract
Let X*(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])not=c(N_G[v]) when N_G[u]not=N_G[v], and c(u)not=c(v) when N_G[u]=N_G[v]. We show that the problem of deciding whether X*(G)=3, is NP-complete for arbitrary graphs. We find X*(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 X*(G) in terms of X(G) and an upper bound is given for X*(G) in terms of Delta(G). For regular graphs with girth at least four we give substantially better upper bounds for X*(G) using random colorings of the vertices.
Recommended Citation
Amin, Ashok, Clark, Lane, McSorley, John P., Wang, Hui and Zhang, Grant. "A Generalized Coloring of Graphs." Journal of Combinatorial Mathematics and Combinatorial Computing 24 (Jan 1997): 49--63.
