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

ABSTRACT 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.