Decomposing Berge Graphs Containing No Proper Wheel, Long Prism Or Their Complements |
| |
| Authors: | Michele Conforti Gérard Cornuéjols Giacomo Zambelli |
| |
| Institution: | (1) Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni, 7, 35131 Padova, Italy;(2) Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, USA;(3) LIF, Faculté des Sciences de Luminy, Université de Marseille, 163 Avenue de Luminy, 13288 Marseille, France;(4) Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni, 7, 35131 Padova, Italy |
| |
| Abstract: | In this paper we show that, if G is a Berge graph such that neither G nor its complement
contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph( a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has
a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect.
This work was supported in part by NSF grant DMI-0352885 and ONR grant N00014-03-1-0188. |
| |
| Keywords: | 05C17 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
