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