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[modifier | modifier le code]

Soient deux graphes $G$ et $H$ . Le produit tensoriel $G\times H$ est défini comme suit^[1] :

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[modifier | modifier le code]

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)\}$ ^[2].

Références[modifier | modifier le code]

↑ (en) Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandstädt et Takao Nishizeki, Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, CRC Press, coll. « Chapman & Hall/CRC Computer and Information Science Series », 2016, 1195 p. (ISBN 9781420011074), Definition 10.5, p. 237
↑ (en) Yaroslav Shitov, « Counterexamples to Hedetniemi's conjecture », Annals of Mathematics, vol. 190, n^o 2,‎ septembre 2019, p. 663–667 (ISSN 0003-486X et 1939-8980, DOI 10.4007/annals.2019.190.2.6, lire en ligne, consulté le 13 juillet 2022)

[1] (en) Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandstädt et Takao Nishizeki, Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, CRC Press, coll. « Chapman & Hall/CRC Computer and Information Science Series », 2016, 1195 p. (ISBN 9781420011074), Definition 10.5, p. 237

[2] (en) Yaroslav Shitov, « Counterexamples to Hedetniemi's conjecture », Annals of Mathematics, vol. 190, n^o 2,‎ septembre 2019, p. 663–667 (ISSN 0003-486X et 1939-8980, DOI 10.4007/annals.2019.190.2.6, lire en ligne, consulté le 13 juillet 2022)

[1]

[2]