Back to Search
Start Over
3-UNIFORM HYPERGRAPHS AND LINEAR CYCLES.
- Source :
-
SIAM Journal on Discrete Mathematics . 2018, Vol. 32 Issue 2, p933-950. 18p. - Publication Year :
- 2018
-
Abstract
- Gyárfás, Győri, 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 α ≥ 2n/5. The hypergraph consisting of vertex disjoint copies of a complete hypergraph K3/5 on five vertices shows that equality can hold. They asked whether this bound can be improved if we exclude K3/5 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 K3 5 as a subhypergraph, then it is 2-colorable. This result clearly implies that its independence number α ≥ [n/2]. We show that this bound is sharp. Gyárfás, Gy}ori, 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 32
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 130882793
- Full Text :
- https://doi.org/10.1137/16M1102367