Factorisation de graphes

vignette|200x200px| Une 1-factorisation du graphe de Desargues : chaque classe de couleur est un 1-facteur. droite|vignette|200x200px| Le graphe de Petersen peut être partitionné en un 1-facteur 1 (en rouge) et un 2-facteur 2 (en bleu). Cependant, le graphe n'est pas 1-factorisable. En théorie des graphes, un facteur d'un graphe G est un graphe partiel, c'est-à-dire un graphe qui a le même ensemble de sommets que G et dont les arêtes sont contenues dans celles de G. Un k -facteur d'un graphe est un graphe partiel k-régulier, et une k-factorisation partitionne les arêtes du graphe en des k-facteurs disjoints. Un graphe G est dit k-factorisable s'il admet une k-factorisation. En particulier, un 1-facteur est une couplage parfait et une 1-factorisation d'un graphe k-régulier est une coloration des arêtes avec k couleurs. Un 2-facteur est une collection de cycles qui couvre tous les sommets du graphe. Un graphe qui est 1-factorisable (c'est-à-dire qui admet une 1-factorisation) est un graphe régulier. La réciproque est fausse : tous les graphes réguliers ne sont pas 1-factorisables. Un graphe k -régulier est 1-factorisable 1 s'il a un indice chromatique égal à k ; des exemples de tels graphes comprennent notamment : Tout graphe biparti régulier. Le théorème de mariage de Hall montre en effet qu'un graphe biparti k-régulier contient un couplage parfait. On peut alors supprimer ce couplage parfait et on obtient a graphe biparti ( k − 1)-régulier, auquel on applique le même raisonnement. Tout graphe complet avec un nombre pair de nœuds (voir aussi ci-dessous ). Il existe également des graphes k-réguliers qui ont un indice chromatique k + 1, et ces graphes ne sont pas 1-factorisables ; des exemples de tels graphies sont : Tout graphe régulier avec un nombre impair de sommets. Le graphe de Petersen . vignette|200x200px| Une 1-factorisation de K 8 ; chaque 1-facteur consiste en une arête du centre à un sommet d'un heptagone avec les trois arêtes parallèles possibles. Une 1-factorisation d'un graphe complet correspond à des couplage dans un tournoi toutes rondes .