Résumé
Le théorème structurel de la série des graphes mineurs de Robertson et Seymour affirme que, pour tout t ∈ N, il existe une constante ct telle que tout graphe K_t-minor-free admet une décomposition en arbre dont les tores peuvent être transformés, par l'élimination d'au plus c_t sommets, en graphes qui peuvent être vus comme l'union d'un graphe incorporable à une surface de genre d'Euler d'au plus ct et "d'au plus c_t tourbillons d'une profondeur de c_t". Notre principal résultat combinatoire est un raffinement "sans vortex" du théorème structurel ci-dessus : nous identifions un graphe (paramétré) H_t, appelé grille de vortex peu profonde, et nous prouvons que si, dans le théorème structurel ci-dessus, nous remplaçons K_t par H_t, alors la décomposition résultante devient "sans vortex". Jusqu'à présent, les classes les plus générales de graphes admettant un tel résultat étaient soit les graphes de genre d'Euler bornés, soit les graphes dits "sans mineur à simple croisement". Notre résultat est étroit dans le sens où, chaque fois que nous excluons par minorité un graphe qui n'est pas mineur d'un certain H_t, l'apparition de tourbillons est inévitable. En utilisant le théorème de décomposition ci-dessus, nous concevons un algorithme qui, étant donné un graphe G sans mineur H_t, calcule la fonction génératrice de toutes les correspondances parfaites de G en temps polynomial. Cet algorithme produit, sur des graphes sans H_t-minor, des algorithmes polynomiaux pour des problèmes de calcul tels que le problème du dimère, le problème de l'appariement exact et le calcul du permanent. Nos résultats, combinés aux résultats de complexité connus, impliquent une caractérisation complète des classes de graphes fermés mineurs où le nombre d'appariements parfaits est polynomialement calculable : Il s'agit exactement des classes de graphes qui ne contiennent pas chaque Ht comme mineur. Ceci fournit une dichotomie de complexité nette pour le problème du comptage des correspondances parfaites dans les classes de graphes fermés mineurs.