Decomposing berge graphs containing no proper wheels, long prisms or their complements
Conforti, M., Cornuéjols, G. & Zambelli, G.
(2006).
Decomposing berge graphs containing no proper wheels, long prisms or their complements.
Combinatorica,
26(5), 533-558.
https://doi.org/10.1007/s00493-006-0031-0
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 | LSE > Academic Departments > Management |
| DOI | 10.1007/s00493-006-0031-0 |
| Date Deposited | 25 Jan 2011 |
| URI | https://researchonline.lse.ac.uk/id/eprint/31699 |
Explore Further
- https://www.scopus.com/pages/publications/33847411447 (Scopus publication)
- http://www.springer.com/mathematics/numbers/journa... (Official URL)