The Existence Of Rainbow Subgraphs And Rainbow Hamiltonian Connectivity In Graph Systems

The problems of graph colorings and the existence of cycles or paths are two core topics in graph theory,which originate from the famous four-color problem and Hamilton problem,respectively.In recent years,determining the existence of rainbow subgraphs in graph systems has become a burgeoning international research topic.This topic amalgamates the graph coloring and extremal problems to delve into the transversal problem of a collection of graphs on the same vertex set.The concept of graph transversal was first raised by Joos and Kim in 2020.We say that G = {Gi: i ∈ [t ]} is a graph system on vertex set V if the vertex set of each graph in G is V.A graph H with vertex set V is a partial transversal in G if there is an injection β : E(H)→ [t] such that e ∈ E(Gβ(e))for each edge e ∈ E(H).In particular,H is a transversal if |E(H)| = t.Equivalently,we can view G as an edge-colored multigraph with V(G)= V and E(G)a multiset consisting of E(G1),...,E(Gt),and an edge e of G is colored by i if e ∈ E(Gi).Therefore,H is a partial transversal if and only if H is a rainbow subgraph of G.Thus,in this thesis,we also call H a rainbow subgraph of G.Aharoni et al.and Joos et al.gave several sufficient conditions for the existences of rainbow triangles and rainbow Hamiltonian cycles in 2020,respectively.Following this research line,this thesis is devoted to the study of the existence of rainbow subgraphs in graph systems,rainbow connectivity,and rainbow panconnectivity.The main content is structured into three sections:Firstly,in the ongoing exploration of the existence of rainbow subgraphs within graph systems,we primarily establish sufficient conditions for the existence of rainbow spanning trees,rainbow Hamiltonian paths and rainbow cliques.Furthermore,we delve into the sufficient conditions for vertex-disjoint rainbow triangles and offer a comprehensive characterization of these results within extremal graphs.Subsequently,we investigate the rainbow pancyclity,rainbow vertex-pancyclicity and rainbow panconnectivity in graph systems,and rainbow vertex-even-pancyclicity and rainbow Hamiltonian connectivity in bipartite graph systems.Additionally,we extend graph systems to directed graph systems,where each graph in the graph system is a directed graph.In the context of directed graph systems,we consider the existence of rainbow Hamiltonian cycles in directed graph systems.In this thesis,we primarily utilize the well-known Absorption Lemma in probability theory to demonstrate rainbow directed version of Dirac theorem in a directed graph system asymptotically.We subsequently provide sufficient conditions for the existence of arbitrary rainbow tournaments in a directed graph system.Finally,we turn our attention to another type of problem in graph system: suppose that each graph in the graph system G satisfies property P.The objective is to determine the minimum value of |G| that guarantees G contains a rainbow subgraph satisfying property P.Aharoni et al.and Dong et al.independently established the minimum value of |G| for the case where property P is that each graph is composed of odd and even cycles.In this thesis,we determine the minimum value of |G| when property P is that each graph consists of star graphs K1,Δand trees,respectively.Furthermore,we provide a comprehensive characterization of extreme graphs in this thesis.