3-uniform hypergraphs and linear cycles
  • Metaadatok
Tartalom: http://real.mtak.hu/71046/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published
Type = Article
Cím:
3-uniform hypergraphs and linear cycles
Létrehozó:
Ergemlidze, Beka
Győri, Ervin
Methuku, Abhishek
Kiadó:
Elsevier
Dátum:
2017
Téma:
QA166-QA166.245 Graphs theory / grĂĄfelmĂŠlet
Tartalmi leírás:
We continue the work of Gyárfás, Győri and Simonovits [Gyárfás, A., E. Győri and M. Simonovits, On 3-uniform hypergraphs without linear cycles. Journal of Combinatorics 7 (2016), 205–216], who proved that if a 3-uniform 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 2-colorable. We answer these questions affirmatively. Namely, we prove that if a 3-uniform linear-cycle-free hypergraph H, doesn't contain K5 3 as a subhypergraph, then it is 2-colorable. 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 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. © 2017 Elsevier B.V.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Ergemlidze, Beka and Győri, Ervin and Methuku, Abhishek (2017) 3-uniform hypergraphs and linear cycles. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 61. pp. 391-394. ISSN 1571-0653
Kapcsolat:
https://doi.org/10.1016/j.endm.2017.06.064
MTMT:3303034; doi:10.1016/j.endm.2017.06.064