Gyárfás–Györi–Simonovits partition conjecture for 3-uniform hypergraphs
Gyárfás–Györi–Simonovits partition conjecture for 3-uniform hypergraphs
Let be a -uniform hypergraph, and let denote the cardinality of a largest independent set of . A linear cycle is a sequence of at least three edges in which only cyclically consecutive edges intersect, and consecutive edges intersect in exactly one vertex. Gyárfás–Györi–Simonovits conjecture. The vertex set of every -uniform hypergraph can be partitioned into linear cycles, edges, and subsets of hyperedges. This conjecture concerns decomposing the vertices of a hypergraph into pieces controlled by its independence number and linear-cycle structure; the source states that it remains open.
Sources & referencesView supporting material
Primary source
András Gyárfás, Ervin Győri and Miklós Simonovits, “On 3-uniform hypergraphs without linear cycles”, arXiv:1412.7205 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.