Nombre de Hadwiger

En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G.

Texte : extrait de l'article Wikipédia « Nombre de Hadwiger », sous licence CC BY-SA 4.0.