Alon–Krivelevich–Sudakov conjecture for K_{s,t}-free graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.