Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T13:54:21.424Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

C. H. C. Little  and
F. Rendl
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.

MSC classification

Secondary: 05C99: None of the above, but in this section
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 46 , Issue 2 , April 1989 , pp. 296 - 301
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. 1051–1079 (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.17–27.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. 241–260, (Ann. Discrete Math. 16, North-Holland Mathematics Studies, North-Holland, Amsterdam).Google Scholar