On the achromatic number of the Cartesian product of two complete graphs
Keywords:Graph, complete vertex colouring, achromatic number, Cartesian product, finite projective plane
A vertex colouring f: V(G) → C of a graph G is complete if for any c1, c2 ∈ C with c1 ≠ c2 there are in G adjacent vertices v1, v2 such that f(v1) = c1 and f(v2) = c2. The achromatic number of G is the maximum number achr(G) of colours in a proper complete vertex colouring of G. Let G1▫G2 denote the Cartesian product of graphs G1 and G2. In the paper achr(Kr2 + r + 1▫Kq) is determined for an infinite number of q’s provided that r is a finite projective plane order.