EUVIMEDEUVIMED entdecken
Crossref

MaxCut in Graphs With Sparse Neighborhoods

Jinghua Deng, Jianfeng Hou, Siwei Lin, Qinghou Zeng

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →