TY - JOUR

T1 - On the Number of Edges in Hypergraphs Critical with Respect to Strong Colourings

AU - Kostochka, Alexandr V.

AU - Woodall, Douglas R.

N1 - Funding Information:
This work was carried out while A. V. Kostochka was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.

PY - 2000/2

Y1 - 2000/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0034412131&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034412131&partnerID=8YFLogxK

U2 - 10.1006/eujc.1999.0330

DO - 10.1006/eujc.1999.0330

M3 - Article

AN - SCOPUS:0034412131

VL - 21

SP - 249

EP - 255

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 2

ER -