Abstract

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.

Notes

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

2019

Semester

Summer

Advisor

Song, Zixia

Degree

Doctor of Philosophy (Ph.D.)

College

College of Sciences

Department

Mathematics

Degree Program

Mathematics

Format

application/pdf

Identifier

CFE0007745

URL

http://purl.fcla.edu/fcla/etd/CFE0007745

Language

English

Release Date

August 2019

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Download

Included in

Mathematics Commons

Share

COinS