TY - JOUR

T1 - Density conditions for panchromatic colourings of hypergraphs

AU - Kostochka, Alexandr V.

AU - Woodall, Douglas R.

N1 - Funding Information:
∗ Th is work was carried out wh ile th e first auth or was visiting Nottingh am, funded by Visiting Fellowsh ip Research Grant GR/L54585 from th e Engineering and Ph ysical Sciences Research Council. Th e work of th is auth or was also partly supported by grants 96-01-01614 and 97-01-01075 of th e Russian Foundation for Fundamental Research .

PY - 2001

Y1 - 2001

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

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

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

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

U2 - 10.1007/s004930100011

DO - 10.1007/s004930100011

M3 - Article

AN - SCOPUS:0039304086

VL - 21

SP - 515

EP - 541

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 4

ER -