1998/07/01 by Michael Krivelevich, Benny Sudakov · 2 citations
Mathematics · #Limits and Structures in Graph Theory
paper · doi:10.1002/(sici)1098-2418(199807)12:4<381::aid-rsa5>3.0.co;2-p
openalex publication_date 1998/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
For a pair of integers 1≤γ<r, the γ-chromatic number of an r-uniform hypergraph H=(V, E) is the minimal k, for which there exists a partition of V into subsets T1,…,Tk such that |e∩Ti|≤γ for every e∈E. In this paper we determine the asymptotic behavior of the γ-chromatic number of the random r-uniform hypergraph Hr(n, p) for all possible values of γ and for all values of p down to p=Θ(n−r+1). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998