EUVIMEDEUVIMED entdecken
Crossref

The Optimal Binding Function for (Cap, Even Hole)‐Free Graphs

Ran Chen, Baogang Xu, Yian Xu

Journal of Graph Theory · 03.08.2026

DOI: 10.1002/jgt.70106 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 03.08.2026. Verfasst von Ran Chen und 2 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A hole is an induced cycle of length at least 4, an even hole is a hole of even length, and a cap is a graph consisting of a hole and an additional vertex which has exactly two neighbors in the hole that are adjacent in the hole. A graph obtained from a graph by blowing up all the vertices into cliques is said to be a clique blowup of . In this paper, we introduce a new method and transfer the optimal binding function problem for the class of (cap, even‐hole)‐free graphs to those with clique number at most 4. Specificly, we show that every (cap, even hole)‐free graph satisfies , which affirmatively answers a question of Cameron et al. [19], we also show that every (cap, even hole, )‐free graph satisfies . Both bounds are tight.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Chen, R., Xu, B., & Xu, Y. (2026). The Optimal Binding Function for (Cap, Even Hole)‐Free Graphs. Journal of Graph Theory. https://doi.org/10.1002/jgt.70106

Vancouver

Chen R, Xu B, Xu Y. The Optimal Binding Function for (Cap, Even Hole)‐Free Graphs. Journal of Graph Theory. 2026. doi:10.1002/jgt.70106

BibTeX
@article{Chen2026,
  author = {Chen, Ran and Xu, Baogang and Xu, Yian},
  title = {The Optimal Binding Function for (Cap, Even Hole)‐Free Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  doi = {10.1002/jgt.70106}
}
Kostenlos starten →