Alon–Bollobás–Krivelevich–Sudakov conjecture on Max-Cut in H-free graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.