Coloring tensor products of graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:47:05Z http://mathoverflow.net/feeds/question/106243 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106243/coloring-tensor-products-of-graphs Coloring tensor products of graphs joro 2012-09-03T13:34:25Z 2012-09-03T14:04:55Z <p>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$.</p> <p>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.</p> <p>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}\}$</p> <p>This is related to <a href="http://garden.irmacs.sfu.ca/?q=op/hedetniemis_conjecture" rel="nofollow">Hedetniemi's Conjecture</a> which states $\chi(G \times H) = \min { \chi(G), \chi(H) }$. </p> <ol> <li>Any counterexamples to this coloring?</li> <li>Is it possible to prove this is valid coloring for certain $G$ or $H$?</li> <li>What types of graphs are potential counterexamples?</li> </ol> http://mathoverflow.net/questions/106243/coloring-tensor-products-of-graphs/106247#106247 Answer by Gjergji Zaimi for Coloring tensor products of graphs Gjergji Zaimi 2012-09-03T14:04:55Z 2012-09-03T14:04:55Z <p>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.</p> <p>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)}$.</p>