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 -