Rainbow paths and trees in properly-colored graphs

Thumbnail Image
Date
2017-01-01
Authors
Wass, Isaac
Major Professor
Advisor
Steven Butler
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Sun Jan 01 00:00:00 UTC 2017