Speaker: Michael Wigal (UIUC)
Title: Longest Path and Cycle Transversals in Chordal Graphs
Abstract: Gallai asked whether the intersection of all longest paths in a connected graph is always nonempty. Now known to not be true, the question remains unresolved for many natural families of graphs. We investigate the problem for chordal graphs. We provide polylogarithmic bounds in terms of the number of vertices for the sizes of smallest hitting sets for longest paths (cycles) in connected (2-connected) chordal graphs. This is the current best bound for both families. This is achieved by a recursive approach on the tree representation of chordal graphs.
Joint work with Kevin G. Milans and James A. Long Jr.
