beta-perfect graphs

Definition $\beta(G)= max_{G' \subseteq G} {(mindeg(G')+1)}$

(the maximum is taken over all induced subgraphs).

Note that $\beta(G) \geq \chi(G)$.

A graph $G$ is called $\beta$-perfect if $\beta(G')=\chi(G')$ for all induced subgraphs $G'$ of $G$.

Question Characterize $\beta$-perfect graphs.

Even holes and graphs obtained from odd holes by replacing every vertex by two adjacent vertices preserving the adjacencies in the hole (so every edge is replaced by a $K_4$) are known not to be $\beta$-perfect. So a $\beta$-perfect graph has no induced subgraph of those types.

Contributed by Bruce Reed

Back to the main index for Perfect Graphs.