ON ψ- CRITICALITY OF SOME RANDOM GRAPHS

ON ψ- CRITICALITY OF SOME RANDOM GRAPHS

S. Kokiladevi, V. Yegnanarayanan, T. Rajermani

[PDF]

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.

Keywords

Random Graphs, Colouring, Pseudoachromatic Number, Vertex ψ-Critical Graphs.