# Factorisation de graphes

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.

## 1-factorisation

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 .

### Graphes complets

Une 1-factorisation d'un graphe complet correspond à des couplage dans un tournoi toutes rondes . La 1-factorisation des graphes complets est un cas particulier d'un théorème de Baranyai (en) concernant la 1-factorisation des hypergraphes complets.
Une méthode de construire d'une 1-factorisation d'un graphe complet avec un nombre pair de sommets consiste à placer tous les sommets sauf un sur un cercle, formant un polygone régulier, avec le sommet restant au centre du cercle. Avec cet arrangement de sommets, on construit un 1-facteur 1 du graphe en choisissant une arête e du centre à un sommet de polygone et on prend de plus les arêtes possibles qui se trouvent sur des droites perpendiculaires à e . Les 1-facteurs construits de cette manière forment une 1-factorisation du graphe.
Le nombre de 1-factorisations distinctes de K $_2$, K $_4$, K $_6$, K $_8$, ... est 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, . . .  A000438 .

### Conjecture de 1-factorisation

Soit G un graphe k-régulier à 2 n nœuds. On sait que si k est suffisamment grand, G est-factorisable ; c'est le cas notamment :
* Si k = 2 n − 1, alors G est le graphe complet K $_{2n}$, et donc 1-factorisable en 1 (voir ci-dessus ).
* Si k = 2 n − 2, alors G peut être construit en supprimant un couplage parfait de K $_{2n}$ . À nouveau, G est 1-factorisable à 1.
* Chetwynd et Hilton (1985) ont montré que si k ≥ 12n/7, alors G est factorisable en 1.
La conjecture de 1-factorisation affirme que k ≈ n est suffisant au sens suivant$^,$$^,$$^,$ :
* Si n est impair et k ≥ n ou si n est pair et k ≥ n − 1, alors G est 1-factorisable.
La conjecture du trop plein (overfull conjecture du graphe trop plein) implique la conjecture de 1-factorisation.

### 1-factorisation parfaite

Un couple parfait issu d'une 1-factorisation est un couple de 1-facteurs dont l'union induit un cycle hamiltonien .
Une 1-factorisation parfaite d'un graphe est une 1-factorisation ayant la propriété que chaque paire de 1-facteurs est une paire parfaite. Une 1-factorisation 1 parfaite ne doit pas être confondue avec un couplage parfait (également appelé un 1-facteur).
En 1964, Anton Kotzig a conjecturé que tout graphe complet K $_{2n}$ pour n ≥ 2 possède une 1-factorisation parfaite. Jusqu'à présent, on sait que les graphes suivants possèdent une 1-factorisation parfaite :
* la famille infinie des graphes complets $K_{2p}$, où p est un nombre premier impair (prouvé par Anderson et aussi par Nakamura, indépendamment),
* la famille infinie des graphes complets $K_{p+1}$, où p est un nombre premier impair,
* et on a des résultats supplémentaires épars, y compris $K_{2n}$ où 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Certains résultats plus récents sont rassemblés ici.
Si un graphe complet $K_{n+1}$ a une 1-factorisation parfaite, alors le graphe biparti complet $K_{n,n}$ a aussi une 1-factorisation parfaite.

## 2-factorisation

Un graphe 2-factorisable doit être 2k -régulier pour un entier k. Julius Petersen a montré en 1891 que cette condition nécessaire est aussi suffisante : tout graphe 2 k -régulier est 2-factorable.
Un graphe connexe 2k -régulier qui a un nombre pair d'arêtes peut être k -factorisé en choisissant pour chacun des deux facteurs une arêtes sur deux d'un chemin d'Euler, pourvu que le graphe est connexe ; des contre-exemples dans le cas non connexe sont notamment les unions disjointes de cycles impairs, ou des copies de $K_{2k+1}$.
Le problème d'Oberwolfach concerne l'existence de 2-factorisations de graphes complets en sous-graphes isomorphes. La question posée est pour quels sous-graphes cela est possible. La réponse est connue lorsque le sous-graphe est connexe, auquel cas c'est un cycle hamiltonien et ce cas particulier est le problème de la décomposition hamiltonienne, mais le cas général reste non résolu.