Some Study On Monochromatic Subgraphs In Edge Colored Graphs

The study of monochromatic subgraphs in edge-colored graphs is always a hot topic graph theory. Bollobas and Gyarfas conjectured that for n≥4k-3every2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2vertices. It was proved that the conjecture holds for k=2,3. Liu et al. proved that every2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2vertices when n≥13k-15. Fujita et al. proved that the same result holds for n≥6.5(k-1). Researchers considered the analogue question in complete multipartite graphs and gave some bounds for the question.In this thesis, we focus on the order of monochromatic k-connected subgraphs in2-edge-colored graphs.In Chapter2, we consider the monochromatic k-connected subgraphs in2-edge-colored complete graph kn. We characterize all the2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n-2k+2vertices for n≥13k-15.In Chapter3, we consider the order of monochromatic2-connected subgraphs in complete multipartite graphs. We give some bounds for the order. Moreover, the upper and lower bounds differ by at most one.Finally, we consider the order of monochromatic4-connected subgraphs in2-edge-colored K4. We show that if each monochromatic k-connected (k=2,3) subgraph has at most n-2k+2vertices in2-edge-colored Kn (n≥13), then there exists a monochromatic4-connected subgraph with at least n-6vertices.