Title: Transversals in covers of graphs
| Speaker: | Krystal Guo |
| Affiliation: | Université Libre de Bruxelles |
| Room: | MC 5501 |
Abstract:
We study a polynomial with connections to correspondence colouring (also known as DP-colouring) and the Unique Games Conjecture. Given a graph G and an assignment of elements of the symmetric group Sr to the edge of G, we define a cover graph: there are sets of r vertices corresponding each vertex of G, called fibres, and for each edge uv, we add a perfect matching between the fibres corresponding to u and v. A transversal subgraph of the cover is an induced subgraph which has exactly one vertex in each fibre. In this setting, we can associate correspondence colourings with transversal cocliques and unique label covers with transversal copies of G.
We define a polynomial which enumerates the transversal subgraphs of G with k edges. We show that this polynomial satisfies a contraction deletion formula and use this to study the evaluation of this polynomial at -r-1. This is joint work with Chris Godsil and Gordon Royle.