MaxCut in Graphs With Sparse Neighborhoods
Journal of Graph Theory · 2026-06 · 112 (2) · 103-115
DOI: 10.1002/jgt.70018 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 13.03.2026. Verfasst von Jinghua Deng und 3 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Deng, J., Hou, J., Lin, S., & Zeng, Q. (2026). MaxCut in Graphs With Sparse Neighborhoods. Journal of Graph Theory, 112(2), 103-115. https://doi.org/10.1002/jgt.70018
Vancouver
Deng J, Hou J, Lin S, Zeng Q. MaxCut in Graphs With Sparse Neighborhoods. Journal of Graph Theory. 2026;112(2):103-115. doi:10.1002/jgt.70018
BibTeX
@article{Deng2026,
author = {Deng, Jinghua and Hou, Jianfeng and Lin, Siwei and Zeng, Qinghou},
title = {MaxCut in Graphs With Sparse Neighborhoods},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {2},
pages = {103--115},
doi = {10.1002/jgt.70018}
}
EUVIMED