Le produit tensoriel est une opération sur deux graphes et résultant en un graphe . Il est également appelé produit direct, produit de Kronecker ou produit catégorique.
Construction Soient deux graphes et . Le produit tensoriel est défini comme suit : l'ensemble de ses sommets est le produit cartésien ; et sont adjacents dans si et seulement si et sont adjacents dans et et sont adjacents dans . 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 est le produit de Kronecker des matrices d'adjacence de et . La concernait le nombre chromatique du produit tensoriel de deux graphes : . Elle est cependant réfutée en 2019 par Yaroslav Shitov qui montre qu'il est possible d'avoir .
Références
Catégorie:Opération sur les graphes