On the Chromatic Number of Simple Triangle-Free Triple Systems

Alan Frieze, Dhruv Mubayi

Abstract


A hypergraph is simple if every two edges share at most one vertex. It is triangle-free if in addition every three pairwise intersecting edges have a vertex in common. We prove that there is an absolute constant $c$ such that the chromatic number of a simple triangle-free triple system with maximum degree $\Delta$ is at most $c\sqrt{\Delta/\log \Delta}$. This extends a result of Johansson about graphs, and is sharp apart from the constant $c$.


Full Text: PDF COMMENT