Chromatic polynomials of hypergraphs

摘要

We consider a natural generalization of the chromatic polynomial of a graph. Let the symbol f(x(1), ...,x(m)) (H, lambda) denote a number of different lambda-colourings of a hypergraph H = (X, epsilon), where X = {nu(1), ..., nu(n)} and epsilon = {e(1), ..., e(m)} satisfying that in an edge e(i) there are used at least xi different colours. In the work we show that f(x(1), ...,x(m)) (H, lambda) can be expressed by a polynomial in. of degree n and as a sum of graph chromatic polynomials. Moreover, we present a reduction formula for calculating f(x(1), ...,x(m)) (H, lambda). It generalizes the similar formulas observed by H. Whitney and R.P. Jones for standard colourings of graphs and hypergraphs respectively. We also study some coefficients of f(x(1), ..., x(m)) (H, lambda) and their connection with the sizes of the edges of H. (c) 2007 Elsevier Ltd. All rights reserved.