An Inequality Related to the Pairs of Matchings of a Graph
Abstract
For a given graph disjoint pairs of matchings the union of which contains as many edges as possible are considered. It is shown that the relation of the cardinality of a maximum matching to the cardinality of the largest matching in those pairs does not exceed 3=2. A conjecture is posed which states that this coeffcient can be replaced by 5=4 . Finally, a family of graphs is presented which shows that the abovementioned coeffcient can not be replaced by a constant which is smaller than 5=4.
References
V. V.Mkrtchyan,On trees with a maximum proper partial 0-1 colouring containing a maximum matching, Discrete Mathematics 306, 2006, pp.455-458.
F.Harary,Graph Theory",Addison-Wesley,Reading,MA,1969.
F.Harary,M.D.Plummer,On the core of a graph,Proc. London Math.Soc.17(1967),305-314.
L.Lovasz,M.D.Plummer,Matching Theory,Annals of Discrete Math.29,North Holland,1986.
D.B.West,Introduction to Graph Theory,Prentice-Hall,Inc,1996.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
