The Optimal Binding Function for (Cap, Even Hole)‐Free Graphs
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.
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}
}
EUVIMED