## Relaxing Perfectness: Which Graphs are 'Almost' Perfect?

Please always quote using this URN: urn:nbn:de:0297-zib-6700

- For all perfect graphs, the stable set polytope STAB$(G)$ coincides with the fractional stable set polytope QSTAB$(G)$, whereas STAB$(G) \subset$ QSTAB$(G)$ holds iff $G$ is imperfect. Padberg asked in the early seventies for ``almost'' perfect graphs. He characterized those graphs for which the difference between STAB$(G)$ and QSTAB$(G)$ is smallest possible. We develop this idea further and define three polytopes between STAB$(G)$ and QSTAB$(G)$ by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB$(G)$. The difference between QSTAB$(G)$ and the largest of the three polytopes coinciding with STAB$(G)$ gives some information on the stage of imperfectness of the graph~$G$. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question: which graphs are ``almost'' perfect?

Author: | Annegret Wagler |
---|---|

Document Type: | ZIB-Report |

Tag: | perfect graph; relaxations; stable set polytope |

MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C17 Perfect graphs |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming | |

Date of first Publication: | 2002/01/22 |

Series (Serial Number): | ZIB-Report (02-03) |

Published in: | Appeared in: The Sharpest Cut - The Impact of Manfred Padberg and His Work. M. GrÃ¶tschel (ed.) MPS-SIAM Series on Optimiztion, 2004, pp. 77-96 |