Concept

Nombre de Hadwiger

Résumé
vignette|upright=1.4|Un graphe avec quatre sous-graphes connectés qui, lorsqu'ils sont contractés, forment un graphe complet. Il ne possède pas de mineur complet à cinq sommets par le théorème de Wagner, donc son nombre de Hadwiger est exactement quatre. 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. Les graphes qui ont un nombre de Hadwiger au plus égal à quatre ont été caractérisés par Wagner en 1937. Les graphes qui ont un nombre de Hadwiger fini borné sont peu denses et ont aussi un petit nombre chromatique. La détermination du nombre de Hadwiger d'un graphe est NP-difficile mais traitable à paramètre fixe. Un graphe G a un nombre de Hadwiger au plus égal à deux si et seulement s'il est une forêt, car un mineur complet à trois sommets ne peut être formé qu'en contractant un cycle de G. Un graphe a un nombre de Hadwiger au plus trois si et seulement si sa largeur arborescente est au plus deux, ce qui est le cas si et seulement si chacune de ses composantes biconnexes est un graphe série-parallèle. vignette|upright=1.4|Une « somme de cliques » de deux graphes planaires et du graphe de Wagner, donnant un graphe de nombre de Hadwiger égal à quatre. Le théorème de Wagner, qui caractérise les graphes planaires par leurs mineurs exclus, implique que les graphes planaires ont un nombre de Hadwiger au plus égal à quatre.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.