首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Sparsely intersecting perfect matchings in cubic graphs
Authors:Edita Máčajová  Martin Škoviera
Institution:1. Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University, 842 48, Bratislava, Slovakia
Abstract:In 1971, Fulkerson made a conjecture that every bridgeless cubic graph contains a family of six perfect matchings such that each edge belongs to exactly two of them; equivalently, such that no three of the matchings have an edge in common. In 1994, Fan and Raspaud proposed a weaker conjecture which requires only three perfect matchings with no edge in common. In this paper we discuss these and other related conjectures and make a step towards Fulkerson’s conjecture by proving the following result: Every bridgeless cubic graph which has a 2-factor with at most two odd circuits contains three perfect matchings with no edge in common.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号