Abstract
We call a graphmatching-covered if every line belongs to a perfect matching. We study the technique of “ear-decompositions” of such graphs. We prove that a non-bipartite matching-covered graph containsK 4 orK 2⊕K 3 (the triangular prism). Using this result, we give new characterizations of those graphs whose matching and covering numbers are equal. We apply these results to the theory of τ-critical graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Andrásfai, On critical graphs, in:Theory of Graphs, Dunod, Paris—Gordon and Breach, New York, (1967) 9–19.
C. Berge, Regularizable graphs I–II,Discrete Math. 23 (1978) 85–89 and 91–95.
R. W. Deming, Independence numbers of graphs — an extension of the König—Egerváry theorem,Discrete Math. 27 (1979) 23–33.
J. Edmonds, Paths, trees and flowers,Can. J. Math. 17 (1965) 449–467.
P. Erdős andT. Gallai, On the minimal number of vertices representing the edges of a graph,Publ. Math. Inst. Hung. Acad. Sci. 4 (1961) 181–205.
T. Gallai, Maximale Systeme unabhängiger Kanten,Publ. Math. Inst. Hung. Acad. Sci. 9 (1965) 401–413.
A. Hajnal, Onk-saturated graphs,Can. J. Math. 17 (1965) 720–724.
D. J. Hartfield, A simplified form for nearly reducible and nearly decomposable matrices,Proc. Amer. Math. Soc. 24 (1970) 388–393.
G. Hetyei, 2×1-es téglalapokkal lefedhető idomokról,Pécsi Tanárképző Főiskola Tud. Kőzl. (1964) 351–368.
A. Kotzig, Ein Beitrag zur Theorie der endlichen Graphen I–II–III,Mat. Fyz. Casopis 9 (1959) 73–91, 136–159, and10 (1960) 205–215.
D. König, Vonalrendszerek és determinánsok,Mat. Term. Ért. 33 (1915) 221–229.
G. H. C. Little, A theorem on connected praphs in which every edge belongs to a 1-factor,J. Austral. Math. Soc. 18 (1974) 450–452.
L. Lovász, On the structure of factorizable graphs,Acta Math. Acad. Sci. Hung. 23 (1972) 179–195.
L. Lovász, Some finite basis theorems an graph theory, in:Combinatorics (ed. A. Hajnal and V. T. Sós), Nort-Holland, 1978, 717–729.
L. Lovász andM. D. Plummer, On bicritical graphs, in:Infinite and Finite sets, (ed. A. Hajnal, R. Rado and V. T. Sós) North-Holland, 1975, 1051–1979.
L. Lovász andM. D. Plummer, On minimal elementary bipartite graphs,J. Comb. Theory B 23 (1977) 127–138.
D. Naddef, Rank of maximum matchings in a graph,Math. Programming (1981).
D. Naddef, andW. R. Pulleyblank, Ear decomposition of elementary graphs andGF 2-rank of perfect matchings,preprint (1981).
M. D. Plummer, Onn-extendable graphs,Discrete Math. 31 (1980) 201–210.
F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number,preprint.
L. Surányi, On line-critical graphs, in:Infinite and Finite Sets (ed. A. Hajnal, R. Rado and V. T. Sós), North-Holland (1975) 1411–1444.
W. T. Tutte, The 1-factors of oriented graphs,Proc. Amer. Math. Soc. 4 (1953) 922–931.
Author information
Authors and Affiliations
Additional information
Dedicated to Tibor Gallai on his seventieth birthday
Rights and permissions
About this article
Cite this article
Lovász, L. Ear-decompositions of matching-covered graphs. Combinatorica 3, 105–117 (1983). https://doi.org/10.1007/BF02579346
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02579346