Search

We consider a natural generalization of the chromatic polynomial of a graph. Let f ( x 1 , … , x m ) ( H , λ ) denote a number of different λ-colourings of a hypergraph H = ( X , E ) , X = { v 1 , … , v n } , E = { e 1 , … e m } , satisfying that in an edge e i it is used at least x i different colours. In the paper we show that f ( x 1 , … , x m ) ( H , λ ) 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 , λ ) . 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 , λ ) and their connection with the sizes of the edges of H .

A subgraph of an edge-coloured graph is rainbow if all of its edges have different colours. For a given a graph H , a rainbow number is the minimum number r b ( n , H ) such that any edge-colouring of K n with at least r b ( n , H ) number of colours contains a rainbow copy of H . We determine the rainbow numbers for certain stars with one edge added and for complete graphs with one edge added.