A colouring of the vertices of a hypergraph G is called strong if, for every edge A, the colours of all vertices in A are distinct. It corresponds to a colouring of the generated graph Γ(G) obtained from G by replacing every edge by a clique. We estimate the minimum number of edges possible in a k-critical t-uniform hypergraph with a given number of vertices. In particular we show that, for k ≥ t + 2, the problem reduces in a way to the corresponding problem for graphs. In the case when the generated graph of the hypergraph has bounded clique number, we give a lower bound that is valid for sufficiently large k and is asymptotically tight in k; this bound also holds for list strong colourings.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics