Faudree–Gyárfás–Schelp star-forest ascending decomposition conjecture

About 3 years old · traced to

Let GG be a graph with (m+12)\binom{m+1}{2} edges. An ascending subgraph decomposition is a decomposition H1,…,HmH_1,\dots,H_m in which HiH_i has ii edges and is a subgraph of Hi+1H_{i+1} for each ii. A star forest is a forest whose connected components are stars. Faudree–Gyárfás–Schelp conjecture. Every graph GG with (m+12)\binom{m+1}{2} edges has an ascending subgraph decomposition H1,…,HmH_1,\dots,H_m in which every HiH_i is a star forest. The paper establishes the broader ascending decomposition conjecture but leaves open whether the decomposition can always be chosen entirely from star forests.

References

Primary source

Kyriakos Katsamaktsis, Shoham Letzter, Alexey Pokrovskiy and Benny Sudakov, “Ascending Subgraph Decomposition”, arXiv:2308.11613 (2023).

Progress summary

Never refreshed

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.