<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2011-07-27T05:50:41.553Z
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 張顯之
CC BY-SA 3.0
2011-07-27T06:03:18.620Z
Hi Hsien: You are correct.
v s
CC BY-SA 3.0
2011-07-27T06:04:17.530Z
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
CC BY-SA 3.0
2011-11-25T04:37:02.853Z
Here is Wikipedia's article on [Hedetniemi's conjecture](http://en.wikipedia.org/wiki/Hedetniemi's_conjecture).
Tyson Williams
CC BY-SA 3.0
2011-11-29T02:31:43.150Z
By $n$-fold strong product do you mean $G\boxtimes G\boxtimes \ldots \boxtimes G$, or $G\boxtimes K_n$?
Andrew D. King
CC BY-SA 3.0
2011-11-29T07:46:17.747Z
@Andrew: The first one
v s
<cc.complexity-theory><graph-theory><graph-colouring>
Question on Products of Graphs
v s
# Question on Products of Graphs

(Asked by: username_0 on 2011-07-27)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-colouring
> **Comments:**
> **username_1**: 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?  
> **username_0**: Hi Hsien: You are correct.  
> **username_0**: 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.  
> **username_2**: Here is Wikipedia's article on [Hedetniemi's conjecture](http://en.wikipedia.org/wiki/Hedetniemi's_conjecture).  
> **username_3**: By $n$-fold strong product do you mean $G\boxtimes G\boxtimes \ldots \boxtimes G$, or $G\boxtimes K_n$?  
> **username_0**: @Andrew: The first one  

---

## 0 answers

