Alon–Bollobás–Krivelevich–Sudakov conjecture on Max-Cut in H-free graphs
Let be a graph. A graph is -free if it contains no subgraph isomorphic to , and for a graph let denote the maximum number of edges in a cut of . Let be the number of edges of .
Alon–Bollobás–Krivelevich–Sudakov conjecture. There exist constants and such that, for all -free graphs ,
This conjecture is presented as a closely related consequence or target of the preceding degeneracy-based conjecture and concerns Max-Cut lower bounds depending only on the edge count. Its general validity is not established in the source.
References
Primary source
Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov and Luca Trevisan, “Lower bounds for Max-Cut in H-free graphs via semidefinite programming”, arXiv:1810.10044 (2020).
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.