On the degree, size, and chromatic index of a uniform hypergraph

Noga Alon, Jeong Han Kim

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)165-170
Number of pages6
JournalJournal of Combinatorial Theory. Series A
Volume77
Issue number1
DOIs
StatePublished - Jan 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On the degree, size, and chromatic index of a uniform hypergraph'. Together they form a unique fingerprint.

Cite this