# 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
Filter by
Sorted by
Tagged with
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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{ ... 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 ... 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 ... 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. ... 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 ... 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 ... 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))... 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 (... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 \... 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 ... 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 ... 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 ... 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 ... 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 \... 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 ... 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 ... 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 ... 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-... 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. ... 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 ... 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? 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 ... 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 ... 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 ... 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... 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 ... 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 ... 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 ... 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 ... 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'' ... 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 ... 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 ... 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 ... 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, ... 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? 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 ...
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 ...