The two-thirds minimum/maximum degree conjecture

About 7 years old · traced to

Let GG be a graph, and let kk be a positive integer. Two-thirds conjecture. If δ(G)≥⌊2k3⌋\delta(G)\ge\left\lfloor\frac{2k}{3}\right\rfloor and Δ(G)≥k\Delta(G)\ge k, then GG contains every tree with kk edges. The conjecture seeks to replace the Erdős–Sós average-degree condition by simultaneous minimum- and maximum-degree conditions. The source records the spanning case and other partial results, but not a general resolution.

References

Primary source

Maya Stein, “Tree containment and degree conditions”, arXiv:1912.04004 (2020).

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.