En théorie des graphes, la conjecture de Sumner (également appelée conjecture universelle du tournoi de Sumner), nommée ainsi d'après David Sumner, affirme que les tournois sont des graphes universels pour les polyarbres. Plus précisément tout tournoi avec sommets contient tout polyarbre avec sommets comme sous-graphe.
Cette conjecture, même si elle est encore ouverte dans le cas général, a été démontré pour toutes les valeurs suffisamment grandes de par Daniela Kühn, Richard Mycroft et Deryk Osthus.
Historique
La formulation de cette conjecture en 1971 est attribuée à David Sumner, un théoricien des graphes à l'université de Caroline du SudLes mentions les plus anciennes de cette conjectures sont attribuées par à et . lui-même cite la conjecture comme étant une communication orale par Sumner, sans date.. La conjecture a été prouvée pour les valeurs assez grandes de par Daniela Kühn, Richard Mycroft et Deryk Osthus,.
A propos de la taille La conjecture de Sumner, si elle est prouvée, donne la plus petite taille possible d'un graphe universel, à savoir 2n-2, pour les polyarbres de taille n.
Pour le voir, considérons le graphe étoile à sommets, dans lequel tous les arcs sont orientés depuis le sommet central vers les feuilles. Alors, ne peut pas être plongé comme sous-graphe dans le tournoi formé à partir des sommets d'un polygone à sommets dont les arêtes sont orientées dans le sens des aiguilles d'une montre autour du polygone. En effet, dans un tel tournoi, tout sommet a un degré entrant et un degré sortant égal à , tandis que le sommet central de a un degré supérieur à Cet exemple est tiré de ..
Cependant, dans un tournoi à sommets, le degré sortant moyen est , et le degré sortant maximal est un nombre entier supérieur ou égal à la moyenne. Il existe donc un sommet de degré sortant , qui peut être utilisé comme sommet central pour une copie de .
Résultats complémentaires Les résultats suivants sur la conjecture ont été prouvés.
Il existe une fonction avec taux de croissance asymptotique avec la propriété que tout polyarbre à sommets peut être plongé comme sous-graphe dans tout tournoi à sommets. De plus, on a la majoration et . D'autres bornes plus faibles et antérieures pour ont été données par , , , , et .. Il existe une fonction telle que les tournois sur les sommets sont universels pour les polyarbres à feuilles; ; .. Il existe une fonction telle que tout polyarbre à sommets de degré au plus peut être plongé comme sous-graphe dans tout tournoi à sommets. Lorsque est une constante fixe, le taux de croissance asymptotique de est . Tout tournoi « quasi régulier » sur sommets contient chaque polyarbre à sommets.. Tout graphe chenille orienté à sommets de diamètre au plus 4 peut être plongé comme sous-graphe dans tout tournoi à sommets. Tout tournoi à sommets contient comme sous-graphe toute arborescence à sommets.
Conjectures associées a conjecturé que toute orientation d'un graphe chemin à sommets peut être plongé comme un sous-graphe dans tout graphe à sommets. Après des résultats partiels de , elle a été prouvée par .
Havet et ThomasséDans , mais attribué conjointement à Thomassé dans l'article. à leur tour ont conjecturé un renforcement de la conjecture de Sumner, dans laquelle tout tournoi sur sommets contient comme sous-graphe tout polyarbre avec au plus feuilles. Cela a été confirmé pour presque tous les arbres par Mycroft et .
a conjecturé que si une coloration d'un graphe requiert au moins couleurs, alors toute orientation de contient toute orientation d'un arbre à sommets. Comme les graphes complets nécessitent une couleur différente pour chaque sommet, la conjecture de Sumner découle immédiatement de la conjecture de BurrCette version correcte de la conjecture est de .. Comme l'a montré Burr, les orientations des graphes dont le nombre chromatique croît quadratiquement en fonction de sont universelles pour les polyarbres.
Notes et références
Bibliographie . . Cité par . . . . . . . . . . . . .
Catégorie:Théorie des graphes Sumner