Degree Type

Thesis

Date of Award

2017

Degree Name

Master of Science

Department

Mathematics

Major

Mathematics

First Advisor

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.

Copyright Owner

Isaac Clarence Wass

Language

en

File Format

application/pdf

File Size

35 pages

Included in

Mathematics Commons

Share

COinS