Path odd-covers of graphs

Combinatorics Seminar
Friday, March 17, 2023 - 3:00pm for 1 hour (actually 50 minutes)
Skiles 249
Youngho Yoo – Texas A&M – yyoo@tamu.edu
Tom Kelly

We study the minimum number of paths needed to express the edge set of a given graph as the symmetric difference of the edge sets of the paths. This can be seen as a weakening of Gallai’s path decomposition problem, and a variant of the “odd cover” problem of Babai and Frankl which asks for the minimum number of complete bipartite graphs whose symmetric difference gives the complete graph. We relate this “path odd-cover” number of a graph to other known graph parameters and prove some bounds. Joint work with Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Frederickson, and Puck Rombach.