Question on Products of Graphs

Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.

Let the chromatic number ($\chi(G)$) and the independence number ($\alpha(G)$) of $G$ be known through a (possibly exponential time) algorithm. Is it known that the calculation of $\chi(S_{n}(G))$, $\chi(C_{n}(G))$, $\chi(T_{n}(G))$,$\alpha(S_{n}(G))$, $\alpha(C_{n}(G))$ and/or $\alpha(T_{n}(G))$ require exponential in $n$ complexity for any $n$ say even when restricted to some special graphs?

• You mean other than the trivial case like $\chi(C_n(G)) = \chi(G)$, or $\chi(T_n(G)) = \chi(G)$ assuming Hedetniemi's Conjecture, right? – Hsien-Chih Chang 張顯之 Jul 27 '11 at 5:50
• Hi Hsien: You are correct. – v s Jul 27 '11 at 6:03
• Hi Hsien: Actually you answered part of the question. If you assume the conjecture, then we already have an $o(0)$ algorithm for those cases. – v s Jul 27 '11 at 6:04
• Here is Wikipedia's article on Hedetniemi's conjecture. – Tyson Williams Nov 25 '11 at 4:37
• By $n$-fold strong product do you mean $G\boxtimes G\boxtimes \ldots \boxtimes G$, or $G\boxtimes K_n$? – Andrew D. King Nov 29 '11 at 2:31