2022/02/06 by Lina Li, Li, Lina, Luke Postle +1 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2202.02839
openalex publication_date 2022/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A triangle in a hypergraph H is a set of three distinct edges e, f, g\inH and three distinct vertices u, v, w∈ V(H) such that \u, v\⊆ e, \v, w\⊆ f, \w, u\⊆ g and \u, v, w\∩ e∩ f∩ g=∅. Johansson proved in 1996 that χ(G)=O(Δ/logΔ) for any triangle-free graph G with maximum degree Δ. Cooper and Mubayi later generalized the Johansson's theorem to all rank 3 hypergraphs. In this paper we provide a common generalization of both these results for all hypergraphs, showing that if H is a rank k, triangle-free hypergraph, then the list chromatic number χℓ(H)≤ O(max2≤ ℓ ≤ k \( \fracΔℓlog Δℓ )(1)/(ℓ-1) \), where Δℓ is the maximum ℓ-degree of H. The result is sharp apart from the constant. Moreover, our result implies, generalizes and improves several earlier results on the chromatic number and also independence number of hypergraphs, while its proof is based on a different approach than prior works in hypergraphs (and therefore provides alternative proofs to them). In particular, as an application, we establish a bound on chromatic number of sparse hypergraphs in which each vertex is contained in few triangles, and thus extend results of Alon, Krivelevich and Sudakov, and Cooper and Mubayi from hypergraphs of rank 2 and 3, respectively, to all hypergraphs.