On pseudocoloring of graphs

Abstract

By a pseudocomplete coloring of a graph G we mean a coloring of the vertices of G such that (i) any two vertices can receive the same color and (ii) between any pair of color classes there is at least one edge. The greatest number of colors used in a pseudocomplete coloring is called the pseudoachromatic number of G. In this paper we investigate the pseudoachromatic number of (a) the join of graphs and (b) various products of graphs.