Extremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain co-critical graphs. Given an integer r ≥ 1 and graphs G; H1; : : : ;Hr, we write → G (H1; : : : ;Hr) if every r-coloring of the edges of G contains a monochromatic copy of Hi in color i for some i ϵ {1; : : : ; r}. A non-complete graph G is (H1; : : : ;Hr)-co-critical if -/ > (H1; : : : ;Hr), but G + uv → (H1; : : : ;Hr) for every pair of non-adjacent vertices u; v in G. Motivated in part by Hanson and Toft's conjecture from 1987, we study the minimum number of edges over all (Kt; Tk)-co-critical graphs on n vertices, where Tk denotes the family of all trees on k vertices. We apply graph bootstrap percolation on a not necessarily Kt-saturated graph to prove that for all t ≥ 4 and k ≥ max{6, t}, there exists a constant c(t, k) such that, for all n ≥ (t - 1)(k - 1) + 1, if G is a (Kt; Tk)-co-critical graph on n vertices, then e(G) ≥ (4t-9/2 + 1/2 [K/2]) n - c _t, k). We then show that this is asymptotically best possible for all sufficiently large n when t ϵ {4, 5} and k ≥ 6. The method we developed may shed some light on solving Hanson and Toft's conjecture, which is wide open. We also study Ramsey numbers of even cycles and paths under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai k-coloring is a Gallai coloring that uses at most k colors. Given an integer k ≥ 1 and graphs H1, : : : ,Hk, the Gallai-Ramsey number GR(H1; : : : ;Hk) is the least integer n such that every Gallai k-coloring of the complete graph Kn contains a monochromatic copy of Hi in color i for some i ϵ {1; : : : ; k}. We completely determine the exact values of GR(H1; : : : ;Hk) for all k ≥ 2 when each Hi is a path or an even cycle on at most 13 vertices.


If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date





Song, Zixia


Doctor of Philosophy (Ph.D.)


College of Sciences



Degree Program










Release Date

August 2019

Length of Campus-only Access


Access Status

Doctoral Dissertation (Open Access)

Included in

Mathematics Commons