Abstract
We study graph theory and combinatorics which are topics in discrete mathematics. The graphs we consider in the thesis consist of a set of vertices and a set of edges in which every edge joins two vertices. An edgecoloring of a graph is an assignment of colors to the edges of the graph.
One fundamental problem in the research of edgecolored graphs is to study the existence of nice substructures in an edgecolored host graph. In this thesis, the nice substructure we consider is either a rainbow subgraph or a monochromatic subgraph, and the host graph is a complete graph. For two graphs G and H, the kcolored GallaiRamsey number is the minimum integer n such that every kedgecoloring of the complete graph on n vertices contains either a rainbow copy of G or a monochromatic copy of H. This concept can be considered as a generalization of the classical Ramsey number.
In this thesis, we determine the exact values of the GallaiRamsey numbers for rainbow triangles and several monochromatic subgraphs. We also obtain some exact values and bounds for the Ramsey numbers and GallaiRamsey numbers of a class of unicyclic graphs. In addition, we contribute some new results related to this research area. In particular, we study an extremal problem related to Gallaicolorings, the GallaiRamsey multiplicity problem, the ErdősGyárfás function with respect to Gallaicolorings, the forbidden rainbow subgraph condition for the existence of a highlyconnected monochromatic subgraph, and the rainbow ErdősRothschild problem with respect to 3term arithmetic progressions.
Throughout this thesis, we present several open problems and conjectures that remain unsolved. In particular, a driving problem is to determine the GallaiRamsey numbers for complete graphs. This problem is related to the classical 2colored Ramsey numbers for complete graphs, and also has a close relationship with the multicolor ErdősHajnal conjecture. Another important problem is to study how does the additional constraint on rainbow triangles influence the classical extremal problems. We hope that these problems and conjectures attract more attention from other researchers.
One fundamental problem in the research of edgecolored graphs is to study the existence of nice substructures in an edgecolored host graph. In this thesis, the nice substructure we consider is either a rainbow subgraph or a monochromatic subgraph, and the host graph is a complete graph. For two graphs G and H, the kcolored GallaiRamsey number is the minimum integer n such that every kedgecoloring of the complete graph on n vertices contains either a rainbow copy of G or a monochromatic copy of H. This concept can be considered as a generalization of the classical Ramsey number.
In this thesis, we determine the exact values of the GallaiRamsey numbers for rainbow triangles and several monochromatic subgraphs. We also obtain some exact values and bounds for the Ramsey numbers and GallaiRamsey numbers of a class of unicyclic graphs. In addition, we contribute some new results related to this research area. In particular, we study an extremal problem related to Gallaicolorings, the GallaiRamsey multiplicity problem, the ErdősGyárfás function with respect to Gallaicolorings, the forbidden rainbow subgraph condition for the existence of a highlyconnected monochromatic subgraph, and the rainbow ErdősRothschild problem with respect to 3term arithmetic progressions.
Throughout this thesis, we present several open problems and conjectures that remain unsolved. In particular, a driving problem is to determine the GallaiRamsey numbers for complete graphs. This problem is related to the classical 2colored Ramsey numbers for complete graphs, and also has a close relationship with the multicolor ErdősHajnal conjecture. Another important problem is to study how does the additional constraint on rainbow triangles influence the classical extremal problems. We hope that these problems and conjectures attract more attention from other researchers.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  21 Oct 2021 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036552486 
Electronic ISBNs  9789036552486 
DOIs  
Publication status  Published  2021 