Density conditions for panchromatic colourings of hypergraphs

Citation
Av. Kostochka et Dr. Woodall, Density conditions for panchromatic colourings of hypergraphs, COMBINATORI, 21(4), 2001, pp. 515-541
Citations number
8
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
21
Issue
4
Year of publication
2001
Pages
515 - 541
Database
ISI
SICI code
0209-9683(2001)21:4<515:DCFPCO>2.0.ZU;2-G
Abstract
Let H = (V, E) be a hypergraph. A panchromatic t-colouring of H is a t-colo uring of its vertices such that each edge has at least one vertex of each c olour; and H is pan chromatically t-choosable if, whenever each vertex is g iven 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 r atio of H is h(H) = min {\ boolean ORF \ / \F \ : 0 not equal F subset of o r equal to E}. Among other results, it is proved here that if every edge ha s at least t vertices and \ boolean ORF \ greater than or equal to (t-1)\F \ -t+3 whenever 0 not equal F subset of or equal to E, then H is panchromat ically t-choosable, and this condition is sharp; the minimum c(t) such that every t-uniform hypergraph with h(H) > alpha is panchromatically t-choosab le satisfies t - 2 + 3/(t + 1) less than or equal to alpha less than or equ al to t - 2 + 4/(t + 2); and except possibly when t = 3 or 5, a t-uniform h ypergraph is panchromatically t-colourable if \ boolean ORF \ greater than or equal to ((t(2) - 2t + 2)\F \ + t - 1)lt whenever 0 not equal F subset o f or equal to E, and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equ al its maximum degree.