Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-05T11:58:00.418Z Has data issue: false hasContentIssue false

An algorithm for the ear decomposition of a 1-factor covered graph

Published online by Cambridge University Press:  09 April 2009

C. H. C. Little
Affiliation:
Department of Mathematics and Statistics, Massey University, Palmerston North, New Zealand
F. Rendl
Affiliation:
Institut für Mathematik Technische Universtät Graz, Kopernikusgasse 24 A-8010 Graz, Austria
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We give a constructive proof for the theorem of Lovász and Plummer which asserts the existence of an ear decomposition of a 1-factor covered graph.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1989

References

[1]Lovász, L. and Plummer, M. D., ‘On bicritical graphs’, Infinite and finite sets II, Colloq. Keszthely, Hungary, 1973, edited by Hajnal, A., Rado, R. and Sós, V. T., pp. 10511079 (Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam, 1975).Google Scholar
[2]Lovász, L. and Plummer, M. D., Matching theory (Ann. Discrete Math. 29, North-Holland Mathematics Studies 121, North-Holland, Amsterdam, 1986).Google Scholar
[3]Micali, S. and Vazirani, V. V., ‘An algorithm for finding maximal matchings in general graphs’, Proc. 21st IEEE Symp. on Foundations of Computer Science, 1980, pp.1727.CrossRefGoogle Scholar
[4]Naddef, D. J. and Pulleyblank, W. R., ‘Ear decompositions of elementary graphs and GF2-rank of perfect matchings’, Bonn workshop on combinatorial optimisation, pp. 241260, (Ann. Discrete Math. 16, North-Holland Mathematics Studies, North-Holland, Amsterdam).Google Scholar