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

Alexandr V. Kostochka, Douglas R. Woodall

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)249-255
Number of pages7
JournalEuropean Journal of Combinatorics
Volume21
Issue number2
DOIs
StatePublished - Feb 2000
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the Number of Edges in Hypergraphs Critical with Respect to Strong Colourings'. Together they form a unique fingerprint.

Cite this