# 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.

108
questions

**1**

vote

**0**answers

31 views

### Perfect matching in hypergraphs: tripartite, regular and unbalanced

In a balanced bipartite graph - where both sides have the same size - a sufficient condition for the existence of a perfect matching is that the graph is regular - all vertices have the same degree.
...

**2**

votes

**0**answers

29 views

### From fractional matching to integral matching in tripartite hypergraphs

Let $G = (X\cup Y, E)$ by a bipartite graph with $n = |X|\leq |Y|$.
A fractional matching is a function assigning a non-negative weight to every edge in $E$, such that the sum of weights near each ...

**0**

votes

**0**answers

15 views

### Complexity of finding matchings with bounds on weight-sum

Question:
what is the complexity of finding a matching of maximal weight-sum below a given bound?
I couldn't find anything in that respect online; maybe only because I do not know what to feed into ...

**0**

votes

**0**answers

15 views

### Criteria for choosing a method for solving bipartite Linear Assignment Problems

For solving the bipartite Linear Assignment Problem there are essentially three methods available:
the variants of the Hungarian algorithm either in matrix or in graph formulation
the Linear ...

**1**

vote

**0**answers

17 views

### Optimal preprocessing in the Kuhn-Munkres algorithm

The matrix formulation of the Kuhn-Munkres algorithm for solving the Linear Assignment Problem requires a preprocessing in which the minimal values of a line be subtracted from every value in that ...

**4**

votes

**2**answers

112 views

### Max weighted matching where edge weight depends on the matching

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...

**9**

votes

**1**answer

125 views

### What graph's minimum vertex cover equals twice the maximum matching?

Matching: https://en.wikipedia.org/wiki/Matching_(graph_theory)
Vertex Cover: https://en.wikipedia.org/wiki/Vertex_cover
It is easy to see that
$$\texttt{minimum vertex cover} \leq 2 \texttt{ ...

**0**

votes

**1**answer

139 views

### Expanding Hall's theorem [closed]

I'm trying to get a "feel" about Hall's theorem and try to expand it for one to many matching.
So my question is:
Given a bipartite graph, what would be a neccessary and sufficient condition for that ...

**1**

vote

**0**answers

26 views

### Matching generating function of 2-lifts

Let $P_G$ denote the matching generating function of a finite simple bipartite graph $G$.
Let now $H$ be a $2$-lift of $G$. We know (see for example Proposition 5.3.3 in Barvinok's book Combinatorics ...

**2**

votes

**2**answers

75 views

### Number of subgraphs with matching of size $n$ for a complete bipartite graph

Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...

**2**

votes

**1**answer

35 views

### maximum weighted matching with weights being sets

Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...

**1**

vote

**1**answer

44 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 ...

**4**

votes

**0**answers

77 views

### Hypergraphs with only disjoint perfect matchings

Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))...

**5**

votes

**1**answer

57 views

### Sizes of matchings and transversals in hypergraphs

Let $H=(V,E)$ be a hypergraph. We call $H$ proper if $E\neq\emptyset, \emptyset \notin E$ and for no $e_1\neq e_2\in E$ we have $e_1\subseteq e_2$. A matching is a set $M$ of pairwise disjoint edges (...

**2**

votes

**1**answer

97 views

### Extending perfect matchings into Hamiltonian cycles

Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...

**0**

votes

**0**answers

49 views

### Decomposition of triangle-free bridgeless planar cubic graphs

Question:
is it true that every triangle-free connected bridgeless planar cubic graph can be decomposed into a vertex-disjoint cycle cover and a single maximal matching of the edges that are adjacent ...

**0**

votes

**0**answers

21 views

### Name for subset selecting matchings

Tutte and also Lovasz and Plummer reduce the calculation of (optimal) f-factors in graph to non-bipartite matching via replacing each vertex with a $K_{f,\delta}$, refered to as a 'gadget' whose ...

**4**

votes

**0**answers

42 views

### Generalization of Menger's Theorem to Infinite Graphs

Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets A and B, there is a family F of disjoint paths from A to B and a set separating B from A consisting ...

**0**

votes

**1**answer

66 views

### Combining three matchings to form a maximal matching

Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...

**3**

votes

**1**answer

39 views

### Practical calculation of minimum weight vertex-disjoint cycle covers

How are minimum-weight vertex-disjoint cycle covers of large dense symmetric graphs actually calculated in actual implementations?
I know that the problem can be reduced to general matching by ...

**3**

votes

**0**answers

64 views

### Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...

**-2**

votes

**2**answers

207 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 $\...

**0**

votes

**1**answer

88 views

### A vertex transitive graph has a near perfect/ matching missing an independent set of vertices

Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...

**3**

votes

**1**answer

118 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$ ...

**1**

vote

**0**answers

101 views

### A simple case of a strong version of the Berge-Fulkerson conjecture

UPDATE 28 June 2019 A counterexample for Conjecture 2 has been provided. The conjecture is now demoted again to guess. The text has been updated to reflect this change, and there is now a new ...

**1**

vote

**0**answers

35 views

### Perfect matchings and edge cuts in cubic graphs - part 1

Let $G$ be a bridgeless cubic (simple) graph, and let $M$ be a perfect matching in $G$. $G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $K_{3,3}$ we ...

**5**

votes

**1**answer

176 views

### On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights

Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...

**2**

votes

**1**answer

84 views

### Number of distinct perfect matchings/near perfect matchings in an induced subgraph

Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is ...

**0**

votes

**1**answer

85 views

### All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $\ge\frac{|V(G)|}{2}$ Class 1(edge-colorable(chromatic index) with $\delta(G)$ colors)? Here, $|V(G)|$ detnotes the number of vertices in the graph.
I ...

**0**

votes

**1**answer

82 views

### Hall theorem with non-saturating matching

Hall's marriage theorem states that given a bipartite graph $G=(X+Y,E)$, if there is no $X$-saturating matching, there there exists $W\subseteq X$ such that $|W|>|N_G(W)|$.
Is the following ...

**10**

votes

**0**answers

523 views

### Has this notion of vertex-coloring of graphs been studied?

In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...

**2**

votes

**0**answers

105 views

### Graph pattern matching

Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time.
...

**5**

votes

**0**answers

191 views

### Can we represent partitions by mutually parallel lines in the plane?

Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...

**2**

votes

**1**answer

150 views

### Graphs with exactly $n$ perfect matchings

Is there for every $n\in\mathbb{N}$ a connected, simple, undirected graph $G_n=(V_n,E_n)$ such that $G_n$ has exactly $n$ perfect matchings?

**0**

votes

**1**answer

86 views

### Connected infinite graphs in which all matchings are “small”

Is there a countable, simple, connected graph $G=(\omega, E)$ such that $\text{deg}(v)$ is infinite for all $v\in \omega$, and for all matchings $M\subseteq E$ the set $V\setminus (\bigcup M)$ is ...

**3**

votes

**1**answer

87 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 ...

**2**

votes

**2**answers

111 views

### Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...

**5**

votes

**2**answers

181 views

### Vertex cover number vs matching number

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$...

**1**

vote

**0**answers

66 views

### Matchings in infinite, not necessarily bipartite, graphs

Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs.
Is there a similar generalization of Tutte's theorem on ...

**0**

votes

**1**answer

112 views

### A weaker version of Dirac's theorem

This is related to Dirac's theorem.
For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal degree of all vertices.
Are there positive integers $n,c\in\mathbb{N}$ with ...

**1**

vote

**0**answers

14 views

### Reducing the Dimension of Rectangular Assignment Matrices

Question:
Given a weighted complete bipartite graph $K_{m,n}(U,V,E)$, $m^2\lt n$, are there any counter examples to the assumption, that the edges of the minimum weight maximal bipartite ...

**11**

votes

**1**answer

531 views

### Graphs with only disjoint perfect matchings, with coloring

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...

**4**

votes

**1**answer

253 views

### Bijection between noncrossing matchings on $2b$ points and Standard Young Tableaux of size $2 \times b$

I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' ...

**3**

votes

**2**answers

246 views

### A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?

Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a ...

**-2**

votes

**1**answer

345 views

### Infinite graphs with large degree but no perfect matching [duplicate]

Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...

**3**

votes

**0**answers

114 views

### Forcing $A_1x,\dotsc,A_Kx$ to lie in a proper subspace

(This is a re-worked version of a question I asked several days ago.)
Let $J$ be the all-one matrix with $m$ rows and $n$ columns, and suppose that $J=A_1+\dotsb+A_K$ is a decomposition of $J$ into a ...

**-2**

votes

**1**answer

72 views

### Matching and minimal degree

Let $n\in\mathbb{N}$ be a positive integer and let $G =(V,E)$ be a connected simple undirected graph with $|V| = 2n$. Is it true that if for the minimal degree $\delta(G)$ we have $\delta(G) \geq n$, ...

**2**

votes

**1**answer

249 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?

**-3**

votes

**1**answer

121 views

### Does the Hadwiger-Nelson graph have a perfect matching?

The Hadwiger-Nelson graph on $\mathbb{R}^n$ is defined to be $(\mathbb{R}^n,E_n)$ where $$E_n = \big\{\{x,y\}: x,y\in \mathbb{R}^n \text{ and } |x-y|=1\big\},$$ where $|\cdot|$ denotes the Euclidean ...

**1**

vote

**1**answer

54 views

### Hall type theorem for saturations of subsets of bipartite graphs

Let $X,Y$ be a bipartite graph and $X',Y'$ be two subsets of the vertices. Is there a Hall type theorem for the existence of matchings saturating both subsets simmultaneously?
Clearly necessary ...