Density conditions for panchromatic colourings of hypergraphs

Alexandr V. Kostochka, Douglas R. Woodall

Research output: Contribution to journalArticlepeer-review


Let H = (V,ε) be a hypergraph. A panchromatic t-colouring of H is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and H is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of H is h(H) = min{|∪ℱ|/|ℱ|:∅≠ℱ⊆δ} Among other results, it is proved here that if every edge has at least t vertices and \∪ℱ| ≥ (t - 1)|ℱ| - t + 3 whenever ∅ ≠ ℱ ⊆ ε, then H is panchromatically t-choosable, and this condition is sharp; the minimum ct such that every t-uniform hypergraph with h(H) > ct is panchromatically t-choosable satisfies t - 2 + 3/(t + 1) ≤ ct ≤ t - 2 + 4/(t + 2); and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if |∪ℱ| ≥ ((t2 - 2t + 2)|ℱ| + t - 1)/t whenever ∅ ≠ ℱ ⊆ ε, and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree.

Original languageEnglish (US)
Pages (from-to)515-541
Number of pages27
Issue number4
StatePublished - 2001

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Density conditions for panchromatic colourings of hypergraphs'. Together they form a unique fingerprint.

Cite this