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?
Question on Products of Graphs
cc.complexity theory;graph theory;graph colouring