3-(v, 4, 1) covering designs with chromatic numbers 2 and 3 |
| |
Authors: | V clav Linek,Eric Mendelsohn |
| |
Affiliation: | Václav Linek,Eric Mendelsohn |
| |
Abstract: | A t-(v, k, λ) covering design is a pair (X, B) where X is a v-set and B is a collection of k-sets in X, called blocks, such that every t element subset of X is contained in at least λ blocks of B. The covering number, Cλ(t, k, v), is the minimum number of blocks a t-(v, k, λ) covering design may have. The chromatic number of (X, B) is the smallest m for which there exists a map φ: X → Zm such that ∣φ((β)∣ ≥2 for all β ∈ B, where φ(β) = {φ(x): x ∈ β}. The system (X, B) is equitably m-chromatic if there is a proper coloring φ with minimal m for which the numbers ∣φ?1(c)∣ c ∈ Zm differ from each other by at most 1. In this article we show that minimum, (i.e., ∣B∣ = C λ (t, k, v)) equitably 3-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0 (mod 6), v ≥ 18 for v ≥ 1, 13 (mod 36), v ≡ 13 and for all numbers v = n, n + 1, where n ≡ 4, 8, 10 (mod 12), n ≥ 16; and n = 6.5a 13b 17c ?4, a + b + c > 0, and n = 14, 62. We also show that minimum, equitably 2-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0, 5, 9 (mod 12), v ≥ 0, v = 2.5a 13b 17c + 1, a + b + c > 0, and v = 23. © 1993 John Wiley & Sons, Inc. |
| |
Keywords: | |
|
|