Invariant de Colin de Verdière
Linvariant de Colin de Verdière est un paramètre de théorie des graphes, défini pour tout graphe, introduit par Yves Colin de Verdière en 1990. Il a été motivé par l'étude de la multiplicité maximale de la seconde valeur propre de certains  opérateurs hamiltoniens.

Définition 
Soit  un graphe simple sans boucle (théorie des graphes)s . On suppose sans perte de généralité que .  Linvariant de Colin de Verdière   est le plus grand  d'une matrice symétrique  telle que :
 (M1) pour tout ,  si , et  si  ;
 (M2)  a exactement une valeur propre négative, de multiplicité 1 ;
 (M3) il n'existe pas de matrices  avec  et telle que  lorsque  ou .

Caractérisation des familles de graphes connues 
Plusieurs familles de graphes bien connues peuvent être caractérisées en termes de leurs invariants de Colin de Verdière :
  si et seulement si  est le graphe nul (sans arêtes);
  si et seulement si  est une   (union disjointe de chaînes);
  si et seulement si  est un graphe planaire extérieur;
  si et seulement si  est un graphe planaire;
  si et seulement si  est un graphe qui admet un 

Ces mêmes familles de graphes apparaissent également dans les connexions entre l'invariant de Colin de Verdière d'un graphe et la structure de son graphe complémentaire : 
 Si le complément d'un graphe à  sommets est une forêt linéaire, alors ;
 Si le complément d'un graphe à  sommets est une graphe planaire extérieur, alors  ;
 Si le complément d'un graphe à  sommets est une graphe planaire, alors .

Mineurs 
Un mineur d'un graphe est un graphe formé à partir du graphe de départ en contractant des arêtes et en supprimant des arêtes et des sommets. L'invariant de Colin de Verdière est décroissant par passage aux mineurs, ce qui signifie qu'un mineur d'un graphe donné a un invariant plus petit que le graphe de départ : 
 On a  pour tout mineur  de .
Par le  théorème de Robertson-Seymour, il existe, pour tout k, un ensemble fini H de graphes tels que les graphes d'invariant au plus  k sont exactement les graphes dont aucun mineur n'est dans  H.  liste ces ensembles de mineurs exclus pour k ≤ 3; for k = 4 l'ensemble des mineurs exclus est composé des sept graphes de la P, due aux deux caractérisations des  comme graphes avec μ ≤ 4 et comme graphes sans mineur dans la famille de. Pour k = 5 l'ensemble des mineurs exclus comprend 78 graphes de la famille de Heawood, et on suppose qu'il n'y a pas d'autres.

Nombre chromatique 
 a conjecturé que tout graphe avec invariant de Colin de Verdière μ peut être coloré avec au plus μ + 1 couleurs. Par exemple; les forêts linéaires ont un invariant inférieur à 1 et sont 2-coloriables; un graphe planaire extérieur a un invariant inférieur à deux, et est 3-coloriable ; les graphes planaires ont un invariant inférieur à 3 et (par le théorème des quatre couleurs) sont 4-coloriables.

Pour les graphes d'invariant au plus quatre, la conjecture reste vraie ; ce sont les graphe avec plongement sans entrelacs, et le fait qu'ils ont un nombre chromatique au plus cinq est un conséquence de la preuve, par Robertson, Seymour et  Thomas, de la Conjecture de Hadwiger pour les graphes sans mineur K6.

Autres propriétés 
Si un graphe a un  nombre de croisements , son invariant de  Colin de Verdière est au plus . Par exemple, les deux graphes de Kuratowski  et  peuvent être tracés avec un seul croisement, et ont un invariant de au plus 4.

Influence 
L'invariant de Colin de Verdière est défini à partir d'une famille particulière de matrices associée à un graphe plutôt qu'une matrice directement définie par le graphe.
Dans cet ordre d'idées, d'autres paramètres de graphes ont été définis et étudiés, tel que lee , le  et le .

Notes

Références 
. Traduit par Neil Calkin : .
.

.
.

Autres publications 
 .
 .

Invariant de graphe
Théorie algébrique des graphes