2019/10/12 by Chris Godsil, Godsil, Chris, Krystal Guo +3
Computer Science · Mathematics · #05C31 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1910.05478
openalex publication_date 2019/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explore the interplay between algebraic combinatorics and algorithmic problems in graph theory by defining a polynomial with connections to correspondence colouring (also known as DP-colouring), a recent generalization of list-colouring, and the Unique Games Conjecture. Like the chromatic polynomial of a graph, we are able to evaluate this polynomial at a point, despite the complexity of computing this polynomial. We construct a cover of a graph X by blowing up each vertex to a set of r vertices and joining each pair of sets corresponding to adjacent vertices by a matching with r edges. To each cover Y of X we associate a polynomial ξ(Y,t), called the transversal polynomial. The coefficient tk of ξ(Y,t) is the number of k-edge induced subgraphs of Y whose vertex set is a transversal of the set system given by the blown-up vertices. We show that ξ(Y,t) satisfies a contraction-deletion formula, and that if n=|VX| and the cover has index r, then ξ(Y,-(r-1)) ≡ 0 \mod rn.