Questions tagged [matching-theory]

For questions about matchings in graph theory. A matching on a graph is a set of edges such that no two edges share a common vertex.

Filter by
Sorted by
Tagged with
21 votes
2 answers
3k views

Graphs with only disjoint perfect matchings

Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings). Examples: Cyclic graph $C_n$ with even ...
Mario Krenn's user avatar
2 votes
1 answer
389 views

Perfect matchings in infinite graphs

Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?
Dominic van der Zypen's user avatar
3 votes
1 answer
3k views

Number of perfect matchings in bipartite graph with given minimum degree

Let $G$ be a spanning subgraph of $K_{n,n}$ with minimum degree $\delta(G) \geq n/2$. It's easy to show using Hall's theorem that $G$ has a perfect matching, and the example of two disjoint copies of ...
Ben Barber's user avatar
  • 4,579
2 votes
2 answers
343 views

Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
Alexi's user avatar
  • 239
1 vote
0 answers
278 views

On Schrijver's lower bound for the number of perfect matchings

Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$...
Turbo's user avatar
  • 13.7k
-1 votes
2 answers
301 views

Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$

If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\...
Dominic van der Zypen's user avatar
30 votes
2 answers
3k views

An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
Sergei Ivanov's user avatar
15 votes
3 answers
600 views

Maximum matching in a graph with no "shortcuts"

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^...
Max Alekseyev's user avatar
8 votes
3 answers
473 views

Problems and algorithms requiring non-bipartite matching

While the importance of the non-bipartite matching problem itself from an algorithmic and complexity point of view is well known, applications of non-bipartite matching are hard to find. I did an ...
Manfred Weis's user avatar
  • 12.6k
8 votes
1 answer
420 views

Fastest algorithm for counting perfect matchings in a general graph

Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$). In particular, what is the ...
Mario Krenn's user avatar
8 votes
2 answers
711 views

Maximum number of perfect matchings in a planar graph?

What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)? Since number of ...
Turbo's user avatar
  • 13.7k
7 votes
1 answer
906 views

Graph to Bipartite conversion preserving number of perfect matchings

Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...
Turbo's user avatar
  • 13.7k
7 votes
1 answer
912 views

Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial: If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
David Bevan's user avatar
7 votes
2 answers
311 views

Perfect matchings of a regular, uniform, partite hypergraph

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
theGrolarBear's user avatar
6 votes
2 answers
7k views

How many perfect matchings in a regular bipartite graph?

We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$. What is an upper bound on the number of perfect matchings of $G$?
pnaky's user avatar
  • 61
6 votes
0 answers
242 views

Catalan numbers from matchings?

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
Per Alexandersson's user avatar
6 votes
2 answers
477 views

Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$. Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
264 views

Perfect matchings in infinite regular bipartite graphs

This question was motivated by a discussion here and is related to a previous question here. Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a ...
Louis D's user avatar
  • 1,666
3 votes
1 answer
98 views

Maximal matchings in connected graphs

Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection? (I ...
Dominic van der Zypen's user avatar
3 votes
1 answer
190 views

Does there exist an r-regular graph (r≥2) with a unique maximum matching?

Akbari, Ghodrati, Hosseinzadeh (2017), On the structure of graphs having a unique k-factor, Aust. J. Combin. (pdf) show: ... we prove that there is no r-regular graph (r≥2) with a unique perfect ...
Rebecca J. Stones's user avatar
3 votes
1 answer
623 views

Equitable edge coloring of graphs

Consider a simple regular graph $G$ with $n$ vertices and $E$ edges. Then, can we say that the edges can be colored equitably in $\Delta+1$ colors? By equitability is meant that a proper $\Delta+1$ ...
vidyarthi's user avatar
  • 2,007
2 votes
0 answers
175 views

Induced matchings in a bipartite graph with every matching having the same number of edges

Suppose $n,k$ are positive integers such that $k\mid n$. Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...
user173856's user avatar
  • 1,987
-1 votes
1 answer
369 views

Marriages in infinite bipartite graphs with many neighbors

Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
Dominic van der Zypen's user avatar