MaxCut in Graphs With Sparse Neighborhoods

ABSTRACT Let be a graph with edges and let denote the number of edges in a largest bipartite subgraph of . The difference is called the surplus of . A fundamental problem in MaxCut is to determine for without specific structure, and the degree sequence of plays a key role in this area. A classical example, given by Shearer, is that for triangle‐free graphs . It was extended to graphs with sparse neighborhoods by Alon, Krivelevich and Sudakov. In this paper, we establish a novel and stronger result for a more general family of graphs with sparse neighborhoods. Our result derives many well‐known bounds on surplus of ‐free graphs for different . Importantly, it can also deduce many new tight bounds when is any graph having a vertex whose removal results in a bipartite graph with Turán exponent at most 3/2, especially the even wheel. This contributes to a conjecture raised by Alon, Krivelevich and Sudakov.