TY - JOUR
T1 - On the degree, size, and chromatic index of a uniform hypergraph
AU - Alon, Noga
AU - Kim, Jeong Han
N1 - Funding Information:
* Research supported in part by a U.S.A. Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences. E-mail: noga math.tau.ac.il. -E-mail: jhkim reseach.att.com.
PY - 1997/1
Y1 - 1997/1
N2 - Let ℋ be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote the maximum degree of a vertex of ℋ. We conjecture that for every ε > 0, if D is sufficiently large as a function of t, k, and ε, then the chromatic index of ℋ is at most (t - 1 + 1/t + ε) D. We prove this conjecture for the special case of intersecting hypergraphs in the following stronger form: If ℋ is an intersecting k-uniform hypergraph in which no two edges share more than t common vertices and D is the maximum degree of a vertex of ℋ, where D is sufficiently large as a function of k, then ℋ has at most (t - 1 + 1/t) D edges.
AB - Let ℋ be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote the maximum degree of a vertex of ℋ. We conjecture that for every ε > 0, if D is sufficiently large as a function of t, k, and ε, then the chromatic index of ℋ is at most (t - 1 + 1/t + ε) D. We prove this conjecture for the special case of intersecting hypergraphs in the following stronger form: If ℋ is an intersecting k-uniform hypergraph in which no two edges share more than t common vertices and D is the maximum degree of a vertex of ℋ, where D is sufficiently large as a function of k, then ℋ has at most (t - 1 + 1/t) D edges.
UR - http://www.scopus.com/inward/record.url?scp=0030641502&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030641502&partnerID=8YFLogxK
U2 - 10.1006/jcta.1996.2728
DO - 10.1006/jcta.1996.2728
M3 - Article
AN - SCOPUS:0030641502
SN - 0097-3165
VL - 77
SP - 165
EP - 170
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 1
ER -