Title: Graphs and Colorful Paths
Speaker: Elizabeth Kupin, Rutgers University
Date: Wednesday, October 5, 2011 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The classical coloring question for a graph is to determine its chromatic number: the minimum number of colors needed in a "proper coloring," that is, one where no two adjacent vertices have the same color. This is number denoted ?(G), and has been studied very extensively. We will look at the related question of determining when a given graph G has a proper coloring with ?(G) colors, with the additional constraint that each vertex is one endpoint of a "rainbow" path of length ?(G) (i.e. no vertices on this path have the same color).
In this talk I'll present some known results about cases when this is possible, a new result of mine, and then highlight some open problems that should be fairly accessible for grad student research. This work came out of participating in the Illinois REGS program, which I highly recommend to grad students who interested in research in Combinatorics and who are currently in their first, second or third years.