Rainbow subgraphs and properly colored subgraphs in colored graphs

Sous-graphes arc-en-ciel et sous-graphes correctement colorés dans les graphes colorés Dans cette thèse, nous étudions les sous graphes arc-en-ciel et les sous-graphes correctement colorés dans les graphes à arêtes colorées, et les sous-graphes compatibles dans les graphes avec des systèmes d'incompatibilité, qui peuvent être considérés comme une généralisation des graphes à arêtes colorées. Par rapport aux graphes généraux, les graphes colorés contiennent plus d'informations et sont capables de modéliser des relations plus complexes dans les réseaux de communication, les sciences sociales, la biologie moléculaire, etc. Par conséquent, l'étude des structures dans les graphes aux arêtes colorées est importante à la fois pour la théorie des graphes et pour d'autres sujets connexes. Nous étudions d'abord la condition de degré de couleur minimum forçant les triangles arc-en-ciel à sommets disjoints dans les graphes aux arêtes colorées. En 2013, Li s'est avéré être la meilleure condition de degré de couleur minimum possible pour l'existence d'un triangle arc-en-ciel. Motivés par cela, nous obtenons une condition de degré de couleur minimum précis garantissant l'existence de deux triangles arc-en-ciel à sommets disjoints et proposons une conjecture sur l'existence de k triangles arc-en-ciel à sommets disjoints. Deuxièmement, nous considérons la relation entre l'ordre de l'arbre maximum correctement coloré dans le graphe à bords colorés et le degré de couleur minimum. On obtient que pour un graphe connexe G aux arêtes colorées, l'ordre du maximum d'arbre correctement coloré est au moins \min\{|G|, 2\delta^{c}(G)\}, ce qui généralise un résultat de Cheng, Kano et Wang. De plus, la borne inférieure 2delta^{c}(G) dans notre résultat est la meilleure possible et nous caractérisons tous les graphes extrémaux. Troisièmement, nous recherchons la condition de degré de couleur minimum garantissant l'existence de 2-facteurs correctement colorés dans les graphes aux bords colorés. Nous dérivons une condition de degré de couleur minimum asymptotique forçant chaque facteur 2 correctement coloré avec exactement t composants, ce qui généralise un résultat de Lo. Nous déterminons également la meilleure condition de degré de couleur minimum possible pour l'existence d'un facteur 2 correctement coloré dans un graphe bipartite à arêtes colorées. Enfin, nous étudions les facteurs compatibles dans les graphes avec des systèmes d'incompatibilité. La notion de système d'incompatibilité a été introduite pour la première fois par Krivelevich, Lee et Sudakov, qui peut être considérée comme une mesure quantitative de la robustesse des propriétés du graphe. Récemment, il y a eu un intérêt croissant pour l'étude de la robustesse des propriétés des graphes, visant à renforcer les résultats classiques en théorie des graphes extrémaux et en combinatoire probabiliste. Nous étudions la version robuste du résultat d'Alon-- Yuster par rapport au système d'incompatibilité.