All Questions
2 questions with no upvoted or accepted answers
8
votes
0
answers
245
views
Sum of perfect matching construction
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.9k
6
votes
0
answers
154
views
Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph
According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...
- 25.4k