Sum-perfect graphs

Abstract

Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph $G$ to be sum-perfect if for every induced subgraph $H$ of $G$, $\alpha (H)+\omega (H)\ge |V(H)|$. (Here $\alpha$ and $\omega$ denote the stability number and clique number, respectively.) We give a set of $27$ graphs and we prove that a graph $G$ is sum-perfect if and only if $G$ does not contain any of the graphs in the set as an induced subgraph.

10 pages, 3 figures