Factorisation de graphes

Une 1-factorisation du graphe de Desargues : chaque classe de couleur est un 1-facteur.

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.

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 de K ₈ ; 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 . 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 ₂, K ₄, K ₆, K ₈, ... 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 ${\displaystyle K_{2p}}$, où p est un nombre premier impair (prouvé par Anderson et aussi par Nakamura, indépendamment),
• la famille infinie des graphes complets ${\displaystyle K_{p+1}}$, où p est un nombre premier impair,
• et on a des résultats supplémentaires épars, y compris ${\displaystyle 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 ${\displaystyle K_{n+1}}$ a une 1-factorisation parfaite, alors le graphe biparti complet ${\displaystyle K_{n,n}}$ 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 ${\displaystyle 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.

Notes et références

1. Harary et 1969 Theorem 9.2, p. 85 ou Diestel et 2005 Corollary 2.1.3, p. 37.
2. Harary et 1969 Theorem 9.1, p. 85.
3. Chetwynd et Hilton 1985.
4. Niessen 1994.
5. Perkovic et Reed 1997.
6. Douglas B. West, « 1-Factorization Conjecture (1985?) », sur faculty.math.illinois.edu.
7. Walter D. Wallis, « 16. Perfect Factorizations », dans One-factorizations, Springer, coll. « Mathematics and Its Applications » (n^o 390), 1997 (ISBN 978-0-7923-4323-3, DOI 10.1007/978-1-4757-2564-3_16), p. 125-130
8. Darryn Bryant, Barbara M. Maenhaut et Ian M. Wanless, « A Family of Perfect Factorisations of Complete Bipartite Graphs », Journal of Combinatorial Theory, A, vol. 98, n^o 2,‎ mai 2002, p. 328–342 (DOI 10.1006/jcta.2001.3240 )
9. Petersen et 1891 §9, p. 200, Harary et 1969 Theorem 9.9, p. 90
10. Petersen et 1891 §6, p. 198.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graph factorization » (voir la liste des auteurs).

Bibliographie

• John Adrian Bondy et U. S. R. Murty, Graph Theory with Applications, North-Holland, 1976 (ISBN 0-444-19451-7, lire en ligne [archive du 13 avril 2010] ), chapitre ( = « Matchings ».
• Amanda G. Chetwynd et Anthony J. W. Hilton, « Regular graphs of high degree are 1-factorizable », Proceedings of the London Mathematical Society, vol. 50, n^o 2,‎ 1985, p. 193–206 (DOI 10.1112/plms/s3-50.2.193).
• Reinhard Diestel, Graph Theory, Springer, 2016-2017, 5^e éd. (ISBN 978-3-662-53621-6, lire en ligne). chapitre 2 : « Matching, covering and packing ».
• Frank Harary, Graph Theory, Addison-Wesley, 1969 (ISBN 0-201-02787-9), chapitre 9: « Factorization ».
• Thomas Niessen, « How to find overfull subgraphs in graphs with large maximum degree », Discrete Applied Mathematics, vol. 51, n^os 1–2,‎ 1994, p. 117–125 (DOI 10.1016/0166-218X(94)90101-5 ).
• Ljubomir Perkovic et Bruce Reed, « Edge coloring regular graphs of high degree », Discrete Mathematics, vol. 165–166,‎ 1997, p. 567–578 (DOI 10.1016/S0012-365X(96)00202-6 ).
• Julius Petersen, « Die Theorie der regulären Graphen », Acta Mathematica, vol. 15,‎ 1891, p. 193–220 (DOI 10.1007/BF02392606 ).
• Douglas B. West, « 1-Factorization Conjecture (1985?) », sur faculty.math.illinois.edu
• (en) Eric W. Weisstein, « Graph Factor », sur MathWorld
• (en) Eric W. Weisstein, « k-Factor », sur MathWorld
• (en) Eric W. Weisstein, « k-Factorable Graph », sur MathWorld
• Michael D. Plummer, « Graph factors and factorization: 1985–2003: A survey », Discrete Mathematics, vol. 307, n^os 7–8,‎ 2007, p. 791–821 (DOI 10.1016/j.disc.2005.11.059 ).