Thesis

2017

#### Degree Name

Master of Science

Mathematics

Mathematics

Steven Butler

#### Abstract

A graph $G$ is \textit{properly $k$-colored} if the colors $\{1,2,\dots,k\}$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge and each color is assigned to some vertex. A \textit{rainbow $k$-path}, a \textit{rainbow $k$-star} and a \textit{rainbow $k$-tree} is a path, star or tree, respectively, on $k$ vertices such that each vertex is a different color. We prove several results about the existence of rainbow paths, stars and trees in properly colored graphs, as well as their uses in proving various criteria about a graph's chromatic number. In particular, any graph $G$ properly colored with the minimum number of colors $\chi(G)$ always contains every possible rainbow $\chi(G)$-tree.

Isaac Clarence Wass

en

application/pdf

35 pages

COinS