Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Entire DC Network
The Regularity Lemma And Its Applications, Elizabeth Sprangel
The Regularity Lemma And Its Applications, Elizabeth Sprangel
Honors Theses
The regularity lemma (also known as Szemerédi's Regularity Lemma) is one of the most powerful tools used in extremal graph theory. In general, the lemma states that every graph has some structure. That is, every graph can be partitioned into a finite number of classes in a way such that the number of edges between any two parts is “regular." This thesis is an introduction to the regularity lemma through its proof and applications. We demonstrate its applications to extremal graph theory, Ramsey theory, and number theory.
Sum-Defined Colorings In Graphs, James Hallas
Sum-Defined Colorings In Graphs, James Hallas
Honors Theses
There have been numerous studies using a variety of methods for the purpose of uniquely distinguishing every two adjacent vertices of a graph. Many of these methods have involved graph colorings. The most studied colorings are proper colorings. A proper coloring of a graph G is an assignment of colors to the vertices of G such that adjacent vertices are assigned distinct colors. The minimum number of colors required in a proper coloring of G is the chromatic number of G. In our work, we introduce a new coloring that induces a (nearly) proper coloring. Two vertices u and …