Date: Wednesday, February 13, 2019
Time: 9:00 – 10:00 a.m.
Location: Building 5700, Conference Room E104
The chromatic number of a graph G is the fewest number of colors one needs so that they can color the vertices of G without any adjacent pair receiving the same color. Many real world problems can be reduced to producing proper colorings of specific graphs. In general, the question of the chromatic number is NP-Complete. In this talk, we will introduce the notion of graph chromatic number and discuss a few related applications. We will then introduce the so-called "Shift Graphs" which were studied by Erdos and Hajnal. Finally, we discuss a generalization of the shift graphs, and provide the chromatic number asymptotically.
This is joint work with Christian Avart, Christiand Reiher, and Vojtech Rodl.
Bill Kay received his Ph.D. in mathematics and M.Sc. in computer science at Emory University in Atlanta, Georgia. He is currently a postdoctoral research fellow, jointly supported by Ryerson University and The Fields Institute in Toronto, Ontario, Canada. His research interests lie at the confluence of discrete mathematics and computer science, with a focus on extremal problems for graphs, hypergraphs, and multigraphs. More recently, his focus has shifted towards machine learning and data analytics.