On the product dimension of clique factors

The product dimension of a graph G is the minimum possible number of proper vertex colorings of G so that for every pair u,v of non-adjacent vertices there is at least one coloring in which u and v have the same color. What is the product dimension Q(s,r) of the vertex disjoint union of r cliques, each of size s? Lovász, Nešetřil and Pultr proved in 1980 that for s=2 it is (1+o(1))log₂r and raised the problem of estimating this function for larger values of s. We show that for every fixed s, the answer is still (1+o(1))log₂r where the o(1) term tends to 0 as r tends to infinity, but the problem of determining the asymptotic behavior of Q(s,r) when s and r grow together remains open. The proof combines linear algebraic tools with the method of Gargano, Körner, and Vaccaro on Sperner capacities of directed graphs.