2010/12/15 by Jacob A. White, Jacob A White, White, Jacob A
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Primary 05C31 Secondary 05C15 Secondary 05C65 #math.CO #msc:05C15 #msc:05C31 #msc:05C65
paper · pdf · doi:10.48550/arxiv.1012.3423
12 pages, 1 figure
arxiv created 2010/12/15 · openalex publication_date 2010/12/15 · arxiv updated 2010/12/16 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
In this paper, we consider multivariate hyperedge elimination polynomials and multivariate chromatic polynomials for hypergraphs. The first set of polynomials is defined in terms of a deletion-contraction-extraction recurrence, previously investigated for graphs by Averbouch, Godlin, and Makowsky. The multivariate chromatic polynomial is an equivalent polynomial defined in terms of colorings, and generalizes the coboundary polynomial of Crapo, and the bivariate chromatic polynomial of Dohmen, Pönitz and Tittman. We show that specializations of these new polynomials recover polynomials which enumerate hyperedge coverings, matchings, transversals, and section hypergraphs. We also prove that the polynomials can be defined in terms of Möbius inversion on the bond lattice of a hypergraph, as well as compute these polynomials for various classes of hypergraphs.