Neighborhood pseudo chromatic polynomial of a path

R. Divya, M. Jayalakshmi


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.

Full Text: PDF

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:


Copyright ©2020 JMCS