×

Optimal ear decompositions of matching covered graphs and bases for the matching lattice. (English) Zbl 1024.05071

A single ear of a graph \(G\) is a path of odd length all of whose internal vertices, if any, have degree equal to two in \(G\). A double ear of \(G\) is a pair of vertex-disjoint single ears of \(G\). An ear decomposition of a matching covered graph \(G\) is a sequence \(G_1\subset G_2\subset \dots \subset G_r\) of matching covered subgraphs of \(G\) where \(G_1=K_2\), \(G_r=G\), and for \(1\leq i\leq r{-}1\), \(G_{i+1}\) is the union of \(G_i\) and an ear (single or double) of \(G_{i+1}\). A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph \(G\), \(b(G)\) denotes the number of bricks of \(G\), and \(p(G)\) denotes the number of Petersen bricks of \(G\). An ear decomposition of \(G\) is optimal if, among all ear decompositions of \(G\), it uses the least possible number of double ears. Applying the main theorem of their two papers [J. Comb. Theory, Ser. B 85, 94-136 (2002; Zbl 1024.05069) and 137-180 (2002; Zbl 1024.05070)], the authors prove that the number of double ears in an optimal ear decomposition of a matching covered graph \(G\) is \(b(G)+p(G)\). Using this theorem, the authors give an alternative proof of the Lovász matching lattice characterization theorem. As a consequence, there is a base of the matching lattice consisting of matchings associated with the optimal ear decomposition.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] de Carvalho, M. H., Decomposição Ótima em Orelhas para Grafos Matching Covered (1997), University of CampinasInstitute of Computing: University of CampinasInstitute of Computing Brazil
[2] de Carvalho, M. H.; Lucchesi, C. L.; Murty, U. S.R., Ear decompositions of matching covered graphs, Combinatorica, 19, 151-174 (1999) · Zbl 0929.05064
[3] M. H. de Carvalho, C. L. Lucchesi, and, U. S. R. Murty, On a conjecture of Lovász concerning bricks, I. The characteristic of a matching covered graph, J. Combin. Theory Ser. B.; M. H. de Carvalho, C. L. Lucchesi, and, U. S. R. Murty, On a conjecture of Lovász concerning bricks, I. The characteristic of a matching covered graph, J. Combin. Theory Ser. B. · Zbl 1024.05069
[4] M. H. de Carvalho, C. L. Lucchesi, and, U. S. R. Murty, On a conjecture of Lovász concerning bricks, II. Bricks of finite characteristic, J. Combin. Theory, Ser. B.; M. H. de Carvalho, C. L. Lucchesi, and, U. S. R. Murty, On a conjecture of Lovász concerning bricks, II. Bricks of finite characteristic, J. Combin. Theory, Ser. B. · Zbl 1024.05070
[5] Edmonds, J.; Lovász, L.; Pulleyblank, W. R., Brick decomposition and the matching rank of graphs, Combinatorica, 2, 247-274 (1982) · Zbl 0521.05035
[6] Lovász, L., Matching structure and the matching lattice, J. Combin. Theory Ser. B, 43, 187-222 (1987) · Zbl 0659.05081
[7] Lovász, L.; Plummer, M. D., Matching Theory. Matching Theory, Annals of Discrete Mathematics, 29 (1986), Elsevier Science: Elsevier Science Amsterdam · Zbl 0618.05001
[8] Murty, U. S.R., The Matching Lattice and Related Topics, Technical report (1994)
[9] Naddef, D., Rank of maximum matchings in a graph, Math. Programming, 22, 52-70 (1982) · Zbl 0468.90052
[10] Naddef, D.; Pulleyblank, W. R., Ear decomposition of elementary graphs and GF (2)-rank of perfect matchings, Ann. Discrete Math., 16, 241-260 (1982) · Zbl 0501.05050
[11] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley · Zbl 0665.90063
[12] Seymour, P. D., On multicolourings of cubic graphs and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. Ser. 3, 38, 423-460 (1979) · Zbl 0411.05037
[13] Szigeti, Z., The two ear theorem on matching-covered graphs, J. Combin. Theory Ser. B, 74, 104-109 (1998) · Zbl 0904.05073
[14] Z. Szigeti, Perfect matchings versus odd cuts, submitted for publication.; Z. Szigeti, Perfect matchings versus odd cuts, submitted for publication. · Zbl 1026.05090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.