On a Conjecture of Fan and Raspaud

We show that every bridgeless cubic graph having a 2-factor with at most two odd circuits admits three perfect matchings with no common edge. This partially verifies a conjecture of Fan and Raspaud (1994) and supports Fulkerson's conjecture (1971).     

Fulkersonʼs Conjecture and Loupekine snarks

Fulkersonʼs Conjecture says that every bridgeless cubic graph has six perfect matchings such that each edge belongs to exactly two of them. In 1976, F. Loupekine created a method for constructing new snarks from already known ones. We consider an infinite family of snarks built with Loupekineʼs method, and verify Fulkersonʼs Conjecture for this family.     

Unions of perfect matchings in cubic graphs

We show that any cubic bridgeless graph with m edges contains two perfect matchings that cover at least 3m/5 and three perfect matchings that cover at least 27m/35 of its edges.     

Non-intersecting perfect matchings in cubic graphs (Extended abstract)

A conjecture of G. Fan and A. Raspaud asserts that every bridgeless cubic graph contains three perfect matchings with empty intersection. We suggest a possible approach to problems of this type, based on the concept of a balanced join in an embedded graph. The method can be used to prove a special case of a conjecture of E. Máčajová and M. Škoviera on Fano colorings of cubic graphs.     

On Cubic Bridgeless Graphs Whose Edge‐Set Cannot be Covered by Four Perfect Matchings

The problem of establishing the number of perfect matchings necessary to cover the edge‐set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP‐complete. We also construct an infinite family of snarks (cyclically 4‐edge‐connected cubic graphs of girth at least 5 and chromatic index 4) whose edge‐set cannot be covered by four perfect matchings. Only two such graphs were known. It turns out that the family also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least , and we show that this inequality is strict for graphs of . We also construct the first known snark with no cycle cover of length less than .     

Exponentially many perfect matchings in cubic graphs

We show that every cubic bridgeless graph G has at least ²|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovász and Plummer.     

On Perfect Matching Coverings and Even Subgraph Coverings

A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3‐edge‐coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so‐called 5‐even subgraph double cover conjecture.     

New conjectures on perfect matchings in cubic graphs

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34.     

The equivalence of two conjectures of Berge and Fulkerson

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1‐factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge‐set of G can be covered with at most five 1‐factors. We prove that the two conjectures are equivalent. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:125‐128, 2011     

3-正则图的不共边的完美匹配（英文）

研究3-正则图的一个有意义的问题是它是否存在k个没有共边的完美匹配.关于这个问题有一个著名的Fan-Raspaud猜想：每一个无割边的3-正则图都有3个没有共边的完美匹配.但这个猜想至今仍未解决.设dim（P（G））表示图G的完美匹配多面体的维数.本文证明了对于无割边的3-正则图G,如果dim（P（G））≤14,那么k≤4：如果dim（P（G））≤20,那么k≤5.     

Cubic bridgeless graphs have more than a linear number of perfect matchings

Lovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve (1979), and for planar graphs by Chudnovsky and Seymour (2008). In this paper, we provide the first superlinear bound in the general case.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

A note on Berge-Fulkerson coloring

The Berge-Fulkerson Conjecture states that every cubic bridgeless graph has six perfect matchings such that every edge of the graph is contained in exactly two of these perfect matchings. In this paper, a useful technical lemma is proved that a cubic graphGadmits a Berge-Fulkerson coloring if and only if the graphGcontains a pair of edge-disjoint matchingsM₁andM₂ such that (i) M₁∪M₂induces a 2-regular subgraph ofG and (ii) the suppressed graph, the graph obtained fromG?M_iby suppressing all degree-2-vertices, is 3-edge-colorable for eachi=1,2. This lemma is further applied in the verification of Berge-Fulkerson Conjecture for some families of non-3-edge-colorable cubic graphs (such as, Goldberg snarks, flower snarks).     

Tutte’s 5-flow conjecture for highly cyclically connected cubic graphs

In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph G. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2. We show that if a cubic graph G has no edge cut with fewer than edges that separates two odd cycles of a minimum 2-factor of G, then G has a nowhere-zero 5-flow. This implies that if a cubic graph G is cyclically n-edge connected and , then G has a nowhere-zero 5-flow.     

Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4

Tutte's 5‐flow conjecture from 1954 states that every bridgeless graph has a nowhere‐zero 5‐flow. It suffices to prove the conjecture for cyclically 6‐edge‐connected cubic graphs. We prove that every cyclically 6‐edge‐connected cubic graph with oddness at most 4 has a nowhere‐zero 5‐flow. This implies that every minimum counterexample to the 5‐flow conjecture has oddness at least 6.     

Transversal matroid intersections and related packings

Network flow techniques are used to show that a conjecture of Fulkerson on the blocking polyhedron associated with the intersection of two matroids is true for transversal matroids. This leads to some general integral packing results for partial transversals, bipartite edge matchings, and subpermutation matrices. A computational example for bipartite edge matchings is included.     

A Note on 5-Cycle Double Covers

The strong cycle double cover conjecture states that for every circuit C of a bridgeless cubic graph G, there is a cycle double cover of G which contains C. We conjecture that there is even a 5-cycle double cover S of G which contains C, i.e. C is a subgraph of one of the five 2-regular subgraphs of S. We prove a necessary and sufficient condition for a 2-regular subgraph to be contained in a 5-cycle double cover of G.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

On Perfect k-Matchings

In this paper, we generalize the notions of perfect matchings, perfect 2-matchings to perfect k-matchings and give a necessary and sufficient condition for the existence of perfect k-matchings. We show that a bipartite graph G contains a perfect k-matching if and only if it contains a perfect matching. Moreover, for regular graphs, we provide a sufficient condition for the existence of perfect k-matching in terms of the edge connectivity.     

双圈覆盖问题

Seyntour[1]与Szekeres[5]猜想，每一个无割边的图G具有一个圈集合 使G中的每个边存在于 的两个圈中。本证明此猜想成立当且仅当它对没有非平凡的三个边割的图成立。