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$.

Published
2008-09-22
Article Number
R121