Computational complexity of pseudoachromatic number of graphs

Abstract

By a pseudocomplete coloring of a graph G we mean a coloring of the vertices of G (not necessarily proper) such that for any two distinct colors, there exist at least one edge in G with these colors on its end vertices. The maximum number of colors used in a pseudocomplete coloring of G is called the pseudoachromatic number of G. In this paper we prove that the pseudoachromatic number problem is NP-complete when restricted to connected graphs that are simultaneously a co-graph and an interval graph. Also we give some upper and lower bounds of this coloring parameter for union of graphs.