Decomposing berge graphs containing no proper wheels, long prisms or their complements
Conforti, Michele; Cornuéjols, Gérard; and Zambelli, Giacomo
(2006)
Decomposing berge graphs containing no proper wheels, long prisms or their complements
Combinatorica, 26 (5).
pp. 533-558.
ISSN 0209-9683
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.
| Item Type | Article |
|---|---|
| Copyright holders | © 2006 J´anos Bolyai Mathematical Society and Springer-Verlag |
| Departments | Management |
| DOI | 10.1007/s00493-006-0031-0 |
| Date Deposited | 25 Jan 2011 15:54 |
| URI | https://researchonline.lse.ac.uk/id/eprint/31699 |
Explore Further
- http://www.springer.com/mathematics/numbers/journa... (Official URL)