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 等数据库收录! |
|