Graphe de Kneser | |
Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen | |
Notation | KGn,k |
---|---|
Nombre de sommets | |
Distribution des degrés | régulier de degré |
Diamètre | |
Nombre chromatique | n-2k+2 |
modifier |
En théorie des graphes, les graphes de Kneser forment une famille infinie de graphes. Le graphe de Kneser KGn,k est un graphe simple dont les sommets correspondent aux sous-ensembles à k éléments d'un ensemble à n éléments. Deux sommets sont reliés s'ils correspondent à des sous-ensembles disjoints. Son ordre est donc égal , le nombre de combinaison de k parmi n, et il est régulier de degré .
En 1955, le mathématicien Martin Kneser se pose la question suivante : « Si on considère la famille des k-sous-ensembles d'un ensemble de cardinal n, on peut partitionner cette famille en n-2k+2 classes de telle façon qu'aucune paire de k-sous-ensembles dans une classe donnée ne soit disjointe. Est-il possible de partitionner la famille considérée en n-2k+1 classes avec la même propriété ? » Kneser conjecture que ce n'est pas possible et le publie sous forme d'un exercice[1].
En 1978 László Lovász étudie la conjecture de Kneser comme un problème de théorie des graphes[2]. Il introduit les graphes de Kneser puis démontre que le nombre chromatique du graphe KGn,k est égal à n-2k+2, ce qui prouve la conjecture de Kneser[3]. L'approche topologique pour résoudre un problème combinatoire est très novatrice et engendre un nouveau domaine : la combinatoire topologique[4].
Le diamètre d'un graphe de Kneser connexe KGn, k, l'excentricité maximale de ses sommets, est égal à[5] :
Quand , le graphe de Kneser KGn, k est hamiltonien[6]. Il est actuellement conjecturé que tous les graphes de Kneser connexes sont hamiltoniens sauf KG5,2, le graphe de Petersen. Une recherche exhaustive sur ordinateur a révélé que cette conjecture était vraie pour [7],[8].
Quand , le graphe de Kneser est un graphe sans triangle. Plus généralement, bien que le graphe de Kneser contienne toujours un cycle de longueur 4 quand , pour des valeurs de proche de , la longueur du cycle impair le plus court dans le graphe de Kneser est variable[9].