List coloring triangle‐free hypergraphs

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 = ∅ . Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number O ( Δ / log Δ ) . Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every linear (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number O ( Δ / log Δ ) . The restriction to linear triple systems was crucial to their proof. We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the linear restriction from [8][A. Frieze, ], while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erdős, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs. As an application, we prove that ifC 3is the collection of 3‐uniform triangles, then the Ramsey number R ( C 3 , K t 3 ) satisfiesa t 3 / 2( log t ) 3 / 4≤ R ( C 3 , K t 3 ) ≤ b t 3 / 2( log t ) 1 / 2for some positive constants a and b . The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that R ( C 3 , K t 3 ) = o ( t 3 / 2 ) where C 3 is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015