title: Produit tensoriel (graphe)
text: # Produit tensoriel (graphe)
  
  Le produit tensoriel est une opération sur deux graphes $G$ et $H$ résultant en un graphe $G\times H$. Il est également appelé produit direct, produit de Kronecker ou produit catégorique.
  
  ## Construction
  
  Soient deux graphes $G$ et $H$. Le produit tensoriel $G\times H$ est défini comme suit :
  
  * l'ensemble de ses sommets est le produit cartésien $V(G)\times V(H)$ ;
  * $(g,h)$ et $(g',h')$ sont adjacents dans $G\times H$ si et seulement si $g$ et $g'$ sont adjacents dans $G$ et $h$ et $h'$ sont adjacents dans $H$. Autrement dit, deux sommets sont voisins si les sommets dont ils sont issus étaient voisins dans les deux graphes.
  
  ## Propriétés
  
  * La matrice d'adjacence de $G\times H$ est le produit de Kronecker des matrices d'adjacence de $G$ et $H$.
  * La conjecture d'Hedetniemi (en) concernait le nombre chromatique du produit tensoriel de deux graphes : $\chi (G\times H)\;{\overset {?}{=}}\;\min\{\chi (G),\chi (H)\}$. Elle est cependant réfutée en 2019 par Yaroslav Shitov qui montre qu'il est possible d'avoir $\chi (G\times H)<\min\{\chi (G),\chi (H)\}$.
  