Alon–Krivelevich–Sudakov conjecture for K_{s,t}-free graphs
Let be a graph with edges, and let denote its surplus, where is the number of edges in a largest bipartite subgraph of . For integers , let be the complete bipartite graph with parts of sizes and , and let be the smallest surplus among all -free graphs with edges. Alon–Krivelevich–Sudakov conjecture. For all and all ,
This is a special case of the general surplus conjecture for forbidden graphs. The source presents it as open and discusses bounds for this family.
References
Primary source
Jinghua Deng, Jianfeng Hou, Siwei Lin and Qinghou Zeng, “MaxCut in graphs with sparse neighborhoods”, arXiv:2307.09309 (2023).
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.