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?

  • 5
    $\begingroup$ 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? $\endgroup$ – Hsien-Chih Chang 張顯之 Jul 27 '11 at 5:50
  • $\begingroup$ Hi Hsien: You are correct. $\endgroup$ – v s Jul 27 '11 at 6:03
  • 1
    $\begingroup$ 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. $\endgroup$ – v s Jul 27 '11 at 6:04
  • 1
    $\begingroup$ Here is Wikipedia's article on Hedetniemi's conjecture. $\endgroup$ – Tyson Williams Nov 25 '11 at 4:37
  • $\begingroup$ By $n$-fold strong product do you mean $G\boxtimes G\boxtimes \ldots \boxtimes G$, or $G\boxtimes K_n$? $\endgroup$ – Andrew D. King Nov 29 '11 at 2:31

Your Answer

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

Browse other questions tagged or ask your own question.