### 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.

**Published:**2019-11-11

**How to Cite this Article:**R. Divya, M. Jayalakshmi, Neighborhood pseudo chromatic polynomial of a path, J. Math. Comput. Sci., 10 (2020), 219-235 Copyright © 2020 R. Divya, M. Jayalakshmi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

J. Math. Comput. Sci.

ISSN: 1927-5307

Editorial Office: jmcs@scik.org

Copyright ©2020 JMCS