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