# Chromatic number of a graph.

Let $S_1, S_2 , \ldots ,S_m$ be finite sets. Let $U=S_1 \times S_2 \times \ldots \times S_m$. Define a graph $G$ with vertex set $U$ such that $x,y \in U$ are adjacent if and only if they differ at exactly one coordinate. Then

(a) $\chi(G)=min\{|S_i| : 1 \leq i \leq m\}$

(b) $\chi(G)=max\{|S_i| : 1 \leq i \leq m\}$

(c) $\chi(G)=\sum\limits_{i=1}^m |S_i|$

(d) None of these

Option (c) is not true: Consider the hyper-cube $Q_2$. Since $Q_2$ obtained with vertex set $\{0,1\} \times \{0,1\}$ with adjacency as described above and its chromatic number is 2.

Further (a) is also not true because if we construct a graph using the vertex set $\{0,1\} \times \{0\}$ we obtain $K_2$ and its chromatic number is 2.

I am unable to prove (or disprove) option (b). It is obvious to me that the chromatic number should be at lest $max\{|S_i| : 1 \leq i \leq m\}=\chi$. This is because such a graph will contain a $\chi$ clique (obtained by keeping all coordinates fixed and varying the coordinate for $S_i$ with $|S_i|=\chi$).

But are $\chi$ colors sufficient? How do I prove that?

## 1 Answer

(b) is true. Let $k=\max\{|S_i|:1\le i\le m\}.$ We may assume that each $S_i$ is a subset of $\{0,1,\dots,k-1\}.$ Now the mapping $$(x_1,x_2,\dots,x_m)\mapsto x_1+x_2+\cdots+x_m\pmod k$$ is a proper coloring, which shows that $\chi(G)\le k.$