3-Uniform Hypergraphs and Linear Cycles

Gyárfás, Gyori, and Simonovits [J. Comb., 7 (2016), pp. 205–216] proved that if a 3-uniform hypergraph with n vertices has no linear cycles, then its independence number α ≥ ² ₅ ⁿ . The hypergraph consisting of vertex disjoint copies of a complete hypergraph K₅ ³ on five vertices shows that equality can hold. They asked whether this bound can be improved if we exclude K₅ ³ as a subhypergraph and whether such a hypergraph is 2-colorable. In this paper, we answer these questions affirmatively. Namely, we prove that if a 3-uniform linear-cycle-free hypergraph doesn’t contain K₅ ³ as a subhypergraph, then it is 2-colorable. This result clearly implies that its independence number α ≥ ⁿ ₂ . We show that this bound is sharp. Gyárfás, Gyori, and Simonovits also proved that a linear-cycle-free 3-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free 3-uniform hypergraph has a vertex of degree at most n − 2 when n ≥ 10.