Factorisation de graphes
From Wikipedia, the free encyclopedia
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[1]. 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[2] (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 2 n, 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 2 n . À nouveau, G est 1-factorisable à 1.
- Chetwynd et Hilton (1985)[3] 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[3],[4],[5],[6] :
- 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 2 n pour n ≥ 2 possède une 1-factorisation parfaite. Jusqu'à présent, on sait que les graphes suivants possèdent une 1-factorisation parfaite[7] :
- la famille infinie des graphes complets , où p est un nombre premier impair (prouvé par Anderson et aussi par Nakamura, indépendamment),
- la famille infinie des graphes complets , où p est un nombre premier impair,
- et on a des résultats supplémentaires épars, y compris 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 a une 1-factorisation parfaite, alors le graphe biparti complet a aussi une 1-factorisation parfaite[8].
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[9].
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[10], 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 .
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.
