1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

(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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.