**Definition**

(the maximum is taken over all induced subgraphs).

Note that .

A graph is called *-perfect* if
for all
induced subgraphs of .

**Question** Characterize -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 ) are known not to be -perfect. So a -perfect graph has no induced subgraph of those types.

Contributed by Bruce Reed

Back to the
main index
for Perfect Graphs.