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
1
vote
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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 ...