On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination

Details On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination

2010-12-15

arxiv.org/abs/1012.3423v1

Mathematics

Combinatorics

12 pages, 1 figure

Scientific paper

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\"onitz 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\"obius inversion on the bond lattice of a hypergraph, as well as compute these polynomials for various classes of hypergraphs.

Affiliated with

Also associated with

No associations

Rating

On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14541