Degrees and Degree Sequences of PAN Critical Graphs

Abstract

A pseudo-complete coloring of a graph G is an assignment of colors to the vertices of G such that for any two distinct colors, there exist adjacent vertices having those colors. The maximum number of colors used in a pseudo-complete coloring of G is called the pseudo-achromatic number of G and is denoted by $\psi_s (G)$. A graph G is called edge critical if $\psi_s (G-e)< \psi_s (G)$ for any edge e of G. A graph G is called vertex critical if $\psi_s (G-v)< \psi_s (G)$ for every vertex v of G. These graphs are generally called as pseudo-achromatic number critical graphs (shortly as PAN Critical graphs). In this paper, we investigate the properties of these critical graphs.