Geodesic
On multivariate chromatic polynomials of hypergraphs and hyperedge elimination
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper we introduce 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 prove that specializations of these new polynomials recover polynomials which enumerate hyperedge coverings, matchings, transversals, and section hypergraphs, all weighted according to certain statistics. We also prove that the polynomials can be defined in terms of Möbius inversion on the partition lattice of a hypergraph, and we compute these polynomials for various classes of hypergraphs. We also consider trivariate polynomials, which we call the hyperedge elimination polynomial and the trivariate chromatic polynomial.
DOI : 10.37236/647
Classification : 05C31, 05C15, 05C65
Mots-clés : multivariate hyperedge elimination polynomials, multivariate chromatic polynomials for hypergraphs 
@article{10_37236_647,
     author = {Jacob A. White},
     title = {On multivariate chromatic polynomials of hypergraphs and hyperedge elimination},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/647},
     zbl = {1337.05059},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/647/}
}
TY  - JOUR
AU  - Jacob A. White
TI  - On multivariate chromatic polynomials of hypergraphs and hyperedge elimination
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/647/
DO  - 10.37236/647
ID  - 10_37236_647
ER  - 
%0 Journal Article
%A Jacob A. White
%T On multivariate chromatic polynomials of hypergraphs and hyperedge elimination
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/647/
%R 10.37236/647
%F 10_37236_647
Jacob A. White. On multivariate chromatic polynomials of hypergraphs and hyperedge elimination. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/647

Cité par Sources :