## Abstract

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_{2}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_{2}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.

Original language | English (US) |
---|---|

Article number | 103097 |

Journal | European Journal of Combinatorics |

Volume | 86 |

DOIs | |

State | Published - May 2020 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics