- Series
- Graph Theory Seminar
- Time
- Tuesday, April 15, 2025 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Peter Bradshaw – UIUC – https://www.peter-bradshaw.com/
- Organizer
- Evelyne Smith-Roberge
We consider the strong parity edge coloring problem, which aims to color the edges of a graph G so that in each open walk on G, some color appears an odd number of times. We show that this problem is equivalent to the problem of embedding a graph in a vector space over F2 so that the number of difference vectors attained at the edges is minimized. Using this equivalence, we achieve the following:
1. We characterize graphs on n vertices that can be embedded with ceil(log_2 n) difference vectors, answering a question of Bunde, Milans, West, and Wu.
2. We show that the number of colors needed for a strong parity edge coloring of K_{s,t} is given by the Hopf-Stiefel function, confirming a conjecture of Bunde, Milans, West, and Wu.
3. We find an asymptotically optimal embedding for the power of a path.
This talk is based on joint work with Sergey Norin and Doug West.