Back to Calendar

Thursday, February 26, 2015

12:00 PM - 1:00 PM (ET)

ESC 184 (Woodhead Lounge)

Event Type

Lecture

Contact

David Constantine, x2167

Department

Academic

Link

https://eaglet.wesleyan.edu/MasterCalendar/EventDetails.aspx?EventDetailId=48394

Abstract: Suppose I have a group of people and I want to know who is a friend of whom. I want to visualize how the people are connected. We can do this by creating a graph in which we have a vertex for each person and we put edges between people who are friends. We can then color the graph by assigning each vertex a color in such a way that if vertices are connected by an edge, that is if people are friends, they are assigned different colors. How many colors will we need? If there is a group of people that are all friends with each other they will each need a different color, this is a clique in the graph. More generally, if there are d people who are all friends with each other then there is a clique of size d (Kd) the graph will require at least d colors. Is the converse true? That is, if we need to use d colors, does this mean there is a clique of size d in the graph? Or are there d people that are all connected in some other way? In terms of graph theory the question is: Does a graph requiring d colors contain a Kd in some way? In this talk we will look at some attempts to answer this question. No prior knowledge of graph theory will be assumed.