Coloring tensor products of graphs

2012-09-03T13:34:25Z

Let $ G,H $ are simple finite graphs and $A = G \times H$. Here $ G \times H $ is the tensor product (also called the direct or categorical product) of $ G $ and $ H $.

Let $G$ has smaller chromatic number. Experiments suggest that given a coloring $f$ of $G$ one can color $A = G \times H$. Color the vertices $(a,b)$ of $A$ with $g(a,b)=f(a), \; a \in V(G)$. Experimentally the coloring is valid.

This was verified for 1000 random graphs and for $\{ \text{Petersen graph}, K_2,K_6, C_5,\text{Star graph 6} ,\text{Random graph of order 14}, \} \times \\ \{\text{All graphs up to 7 vertices}\}$

This is related to Hedetniemi's Conjecture which states $ \chi(G \times H) = \min { \chi(G), \chi(H) } $.

Any counterexamples to this coloring?
Is it possible to prove this is valid coloring for certain $G$ or $H$?
What types of graphs are potential counterexamples?

Answer by Gjergji Zaimi for Coloring tensor products of graphs

2012-09-03T14:04:55Z

The only way that two vertices $(u,v)$ and $(u',v')$ end up getting the same color is if $f(u)=f(u')$. But then there is no edge between $u$ and $u'$ in $G$ so there is no edge between $(u,v)$ and $(u',v')$ in $G\times H$. So your conjecture is true for all graphs.

In fact, as explained in the page you linked to above, a coloring with $n$ colors is simply a graph homomorphism to $K_n$, the complete graph on $n$ vertices. Since we have a homomorphism $G\times H\to G$ we can simply compose this with a homomorphism $G\to K_n$ whenever $\chi(G)=n$. This gives your construction. It also proves that $\chi(G\times H)\le \min{\chi(G),\chi(H)}$.

Coloring tensor products of graphs - MathOverflow

Coloring tensor products of graphs

Answer by Gjergji Zaimi for Coloring tensor products of graphs