Carlson et al.'s Shearer-type surplus conjecture for clique-free graphs
Carlson et al.'s Shearer-type surplus conjecture for clique-free graphs
Let be fixed. A graph is -degenerate if every subgraph has a vertex of degree at most , and denotes the complete graph on vertices. For a graph with edges, let its surplus be the quantity measuring the excess of its maximum cut over the baseline determined by its number of edges.
Carlson et al.'s conjecture. Every -free -degenerate graph with edges has surplus
Carlson et al. proposed this as an analogue of Shearer's bound for -free graphs and showed that it would imply the conjecture of Alon, Bollobás, Krivelevich and Sudakov on surplus in -free graphs. The supplied material does not state whether this conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Stefan Glock, Oliver Janzer and Benny Sudakov, “New results for MaxCut in H-free graphs”, arXiv:2104.06971 (2021).
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.