On the achromatic number of the Cartesian product of two complete graphs

Abstract

A vertex colouring f: V(G) → C of a graph G is complete if for any c₁, c₂ ∈ C with c₁ ≠ c₂ there are in G adjacent vertices v₁, v₂ such that f(v₁) = c₁ and f(v₂) = c₂. The achromatic number of G is the maximum number achr(G) of colours in a proper complete vertex colouring of G. Let G₁▫G₂ denote the Cartesian product of graphs G₁ and G₂. In the paper achr(K_{r² + r + 1}▫K_q) is determined for an infinite number of q’s provided that r is a finite projective plane order.