Pikhurko–Sousa conjecture on asymptotic extremal decompositions
Let be a graph with chromatic number at least . For an -vertex graph , let be the minimum number of parts in an edge partition into copies of and single edges, and define . Let denote the maximum number of edges in an -vertex graph containing no copy of .
Pikhurko–Sousa conjecture. There is an integer such that
for every .
Pikhurko and Sousa had previously established the asymptotic relation for each fixed graph with chromatic number at least ; the conjecture asks for eventual exact equality.
References
Primary source
Lale Özkahya and Yury Person, “Minimum Rainbow H-Decompositions of Graphs”, arXiv:1704.01000 (2017).
Additional references
2 papers in this index state this conjecture (2011–2017). The statement above is taken from the most recent of them; the others are arXiv:1109.2571.
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
No solutions have been posted yet.