Neighborhood pseudo chromatic polynomial of a path

Abstract

Let N(v) = {x: vx ∈ E(G)} be the open neighborhood and N[v] = N(v)∪{v} be the closed neighborhood of a vertex v ∈V. A neighborhood pseudo coloring of a connected graph G(V,E) is a function c: V → {1,2,··· , k} such that for each vertex v ∈ V, there exists at least two vertices u,w ∈ N[v] with c(u) = c(w). A neighborhood pseudo coloring c: V → {1,2,···, k} which is surjective, is called neighborhood pseudo k−coloring and the maximum k for which G admits a neighborhood pseudo k−coloring is called the neighborhood pseudo chromatic number of G, denoted by ψnhd(G). Chromatic polynomials are defined and studied for various types of proper coloring. In this paper, we initiate the study of neighborhood pseudo chromatic polynomial of a graph G as a polynomial in λ to count the number of distinct ways to neighborhood pseudo color G with atmost λ colors. Neighborhood pseudo chromatic polynomial of a path Pn is determined with a recurrence relation for its coefficients. Further an efficient algorithm is developed for its evaluation.