On ψ- criticality of some random graphs

Abstract

A vertex colouring g of a graph G is said to be pseudocomplete if for any two distinct colours i, j there exists at least one edge e = (u, v) ∈ E(G) such that g(u) = i and g(v) = j. The maximum number of colors used in a pseudocomplete coloring is called the pseudoachromatic number ψ(G) of G. A Graph G is called vertex ψ-critical if ω(G) = 2ψ(G) − |V (G)|. If P* is a criticality property with respect to ψ then we have obtained some interesting results related to the random graphs as process innovation. We also proved that there is positive probability for the existence of a large collection of family of graphs that are not critical. We also listed a number of open problems.