zbMATH — the first resource for mathematics

On the choice number of packings. (English) Zbl 1258.05038
Summary: In this note, we show that for positive integers \(s\) and \(k\), there is a function \(D(s,k)\) such that every \(t\)-\((v,k,\lambda)\) packing with at least \(D(s,k)\lambda ^{k-t}s^{t-2} v \binom{v-2}{t-2}/\binom{k-2}{t-2}\) edges, \(2 \leq t \leq k-1\), has choice number greater than \(s\).
Consequently, for integers \(s\), \(k\), \(t\), and \(\lambda \) there is a \(v_{0}(s,k,t,\lambda)\) such that every \(t\)-\((v,k,\lambda)\) design with \(v > v_{0}(s,k,t,\lambda)\) has choice number greater than \(s\).
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] N. Alon A. Kostochka Hypergraph list coloring and Euclidean Ramsey Theory, Random Structures Algorithms 39 2011 377 390
[2] N. Alon A. Kostochka Dense uniform hypergraphs have high list chromatic number Discrete Math · Zbl 1244.05156
[3] R. Diestel Graph Theory, Fourth Edition, Graduate Texts in Mathematics, 173, Springer, Heidelberg 2010
[4] Haxell, On list coloring Steiner triple systems, J Combin Des 17 pp 314– (2009) · Zbl 1222.05060 · doi:10.1002/jcd.20215
[5] Haxell, List coloring hypergraphs, Electron J Combin 17 (2010) · Zbl 1277.05062
[6] Kahn, Asymptotically good list-colorings, J Combin Theory Ser A 73 pp 1– (1996) · Zbl 0851.05081 · doi:10.1006/jcta.1996.0001
[7] Kostochka, The colour theorems of Brooks and Gallai extended, Discrete Math 162 pp 299– (1996) · Zbl 0871.05024 · doi:10.1016/0012-365X(95)00294-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.