What question did this study set out to answer?

To derive new bounds on the surplus of certain types of graphs with sparse neighborhoods and explore implications for known conjectures.

March 15, 2026

MaxCut in Graphs With Sparse Neighborhoods

Key Points

To derive new bounds on the surplus of certain types of graphs with sparse neighborhoods and explore implications for known conjectures.
Analyzed the surplus of bipartite subgraphs in general classes of sparse neighborhood graphs.
Extended classical results by Shearer and others regarding triangle-free graphs.
Developed a framework to deduce new bounds related to vertex removal leading to bipartite graphs.
Established novel bounds on the surplus for bipartite subgraphs in sparse neighborhood graphs.
Provided tighter bounds for graphs with specific properties, including those leading to a bipartite structure with Turán exponent of 3/2.
Contributed insights towards conjectures related to bipartite graphs raised by Alon, Krivelevich, and Sudakov.

Abstract

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.

Mark Helpful

Bookmark

Relay