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 -