2013/02/15 by Jeff Cooper, Cooper, Jeff, Dhruv Mubayi +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1302.3872
openalex publication_date 2013/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A triangle in a hypergraph is a collection of distinct vertices u,v,w and distinct edges e,f,g with u,v ∈ e, v,w ∈ f, w,u ∈ g, and \u,v,w\ ∩ e ∩ f ∩ g=∅. The i-degree of a vertex in a hypergraph is the number of edges of size i containing it. We prove that every triangle-free hypergraph of rank three (edges have size two or three) with maximum 3-degree Δ3 and maximum 2-degree Δ2 has list chromatic number at most c maxΔ2/ logΔ2, (Δ3 / logΔ3)^(1/2) for some absolute positive constant c. This generalizes a result of Johansson and a result of Frieze and the second author.