Chromatic polynomials of hypergraphs (Q5920448)

The authors investigate the number of \(\lambda\)-colourings of the vertices of a hypergraph \(H\) such that each edge \(e_i\) of \(H\) contains at least \(x_i\) differently coloured vertices for given quantities \(x_1,\dots,x_m\) (one for each edge). They show that the number of such colourings can be expressed as a polynomial of degree \(n\) (the number of vertices of \(H\)) and as a sum of chromatic polynomials, and present a reduction formula generalizing similar formulae for standard colourings of graphs and hypergraphs.