Ergemlidze, Beka and Győri, Ervin and Methuku, Abhishek (2017) 3uniform hypergraphs and linear cycles. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 61. pp. 391394. ISSN 15710653

Text
1609.03934v2.pdf Download (232kB)  Preview 
Abstract
We continue the work of Gyárfás, Győri and Simonovits [Gyárfás, A., E. Győri and M. Simonovits, On 3uniform hypergraphs without linear cycles. Journal of Combinatorics 7 (2016), 205–216], who proved that if a 3uniform hypergraph H with n vertices has no linear cycles, then its independence number α≥[Formula presented]. The hypergraph consisting of vertex disjoint copies of complete hypergraphs K5 3 shows that equality can hold. They asked whether α can be improved if we exclude K5 3 as a subhypergraph and whether such a hypergraph is 2colorable. We answer these questions affirmatively. Namely, we prove that if a 3uniform linearcyclefree hypergraph H, doesn't contain K5 3 as a subhypergraph, then it is 2colorable. This result clearly implies that α≥⌈[Formula presented]⌉. We show that this bound is sharp. Gyárfás, Győri and Simonovits also proved that a linearcyclefree 3uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linearcyclefree 3uniform hypergraph has a vertex of degree at most n−2 when n≥10. © 2017 Elsevier B.V.
Item Type:  Article 

Uncontrolled Keywords:  Loose cycle; linear cycle; Independence number 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  13 Dec 2017 14:17 
Last Modified:  13 Dec 2017 14:17 
URI:  http://real.mtak.hu/id/eprint/71046 
Actions (login required)
Edit Item 