Colouring of Voloshin for ATS(v)

  • Alberto Amato


A mixed hypergraph is a triple H=(S,C,D), where S is the vertex set and each of C,D is a family of not-empty subsets of S, the C-edges and D-edges respectively. A strict k-colouring of H is a surjection f  from the vertex set into a set of colours {1, 2, . . . , k} so that each C-edge contains at least two distinct vertices x, y such that f(x) = f(y) and each D-edge contains at least two vertices x, y such that f(x)=f(y). For each k ∈ {1, 2, . . . , |S|}, let r_k be the number of partitions of the vertex set into k not-empty parts (the colour classes) such that the colouring constraint is satisfied on each C-edge and D-edge. The vector R(H ) = (r_1 , . . . , r_k ) is called the chromatic spectrum of H. These concepts were introduced by V. Voloshin in 1993 [6].

In this paper we examine colourings of mixed hypergraphs in the case that H is an ATS(v).