- Series
- Graph Theory Seminar
- Time
- Thursday, February 7, 2013 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Chun-Hung Liu – Math, GT
- Organizer
- Robin Thomas
A (5,2)-configuration in a graph G is a function which maps the
vertices of G into 2-element subsets of {1,2,3,4,5} in such a way that
for every vertex u, the union of the 2-element subsets assigned to u and
all its neighbors is {1,2,3,4,5}. This notion is motivated by a problem in robotics. Fujita, Yamashita and Kameda showed
that every 3-regular graph has a (5,2)-configuration. In this talk, we will prove that except for four graphs, every
graph of minimum degree at least two which does not contain K_{1,6} as
an induced subgraph has a (5,2)-configuration. This is joint work with Waseem Abbas, Magnus Egerstedt, Robin Thomas, and Peter Whalen.