Invariant de Colin de Verdière

LModèle:'invariant 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 $G=(V,E)$ un graphe simple sans boucle. On suppose sans perte de généralité que $V=\{1,\dots ,n\}$. LModèle:'invariant de Colin de Verdière $\mu (G)$ est le plus grand Modèle:Lien d'une matrice symétrique $M=(M_{i,j})\in {ℝ}^{n\times n}$ telle que :

• (M1) pour tout $i\ne j$, $M_{i,j}<0$ si $\{i,j\}\in E$, et $M_{i,j}=0$ si $\{i,j\}\notin E$ ;
• (M2) $M$ a exactement une valeur propre négative, de multiplicité 1 ;
• (M3) il n'existe pas de matrices $X=(X_{i,j})\in {ℝ}^{n\times n}$ avec $MX=0$ et telle que $X_{i,j}=0$ lorsque $i=j$ ou $M_{i,j}\ne 0$Modèle:,.

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 :

• $\mu (G)\le 0$ si et seulement si $G$ est le graphe nul (sans arêtes)Modèle:,;
• $\mu (G)\le 1$ si et seulement si $G$ est une Modèle:Lien (union disjointe de chaînes)Modèle:,;
• $\mu (G)\le 2$ si et seulement si $G$ est un graphe planaire extérieurModèle:,;
• $\mu (G)\le 3$ si et seulement si $G$ est un graphe planaireModèle:,;
• $\mu (G)\le 4$ si et seulement si $G$ est un graphe qui admet un Modèle:LienModèle:,

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 à $n$ sommets est une forêt linéaire, alors $\mu \ge n-3$Modèle:,;
• Si le complément d'un graphe à $n$ sommets est une graphe planaire extérieur, alors $\mu \ge n-4$Modèle:,;
• Si le complément d'un graphe à $n$ sommets est une graphe planaire, alors $\mu \ge n-4$Modèle:,.

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 $\mu (H)\le \mu (G)$ pour tout mineur $H$ de $G$.

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. Modèle:Harvsp 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 Modèle:Lien 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

Modèle:Harvsp 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 K₆.

Autres propriétés

Si un graphe a un nombre de croisements $k$, son invariant de Colin de Verdière est au plus $k+3$. Par exemple, les deux graphes de Kuratowski $K_5$ et $K_{3,3}$ 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ées à 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 le Modèle:Lien, le rang minimum semidéfini d'un graphe et le rang gauche minimum d'un graphe.

Références

• Modèle:Article. Traduit par Neil Calkin : Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article.

Autres publications

• Modèle:Ouvrage.
• Modèle:Article.