# Questions tagged [perfect-matchings]

A perfect matching is a matching of all the vertices of a graph. In other words, a perfect matching is a set of edges such that each vertex of the graph is incident to exactly one edge in the set.

76
questions

**0**

votes

**0**answers

4 views

### Perfect matching for a particular type of bipartite graphs

Let $G = (V_1 \cup V_2, E)$ be a connected and bipartite graph such that:
(1) The number of vertices of $V_1$ is equal to the number of vertices of $V_2$, i.e., $|V_1| = |V_2| = N$ for some $N \in \...

**0**

votes

**1**answer

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

**-2**

votes

**2**answers

170 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

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

**1**

vote

**0**answers

86 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

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

**0**

votes

**0**answers

34 views

### Biadjacency permanent upper bound in terms of genus of graph?

Take $M$ to be biadjacency of a planar balanced bipartite on $2n$ vertices with genus $g$.
Is it true for every $\epsilon\in(0,1)$ there is a $c_\epsilon>0$ such that $$\log\log(permanent(M))\leq\...

**0**

votes

**0**answers

10 views

### On statistics of perfect matchings between planar $4$ colorable and planar $3$ colorable

Does the mean for number of perfect matchings of random graphs that are planar and $3$ colorable much higher than graphs that are planar are not $3$ colorable?
Does a planar graph if $3$ colorable ...

**1**

vote

**1**answer

52 views

### Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph

What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...

**5**

votes

**1**answer

137 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

**0**answers

30 views

### Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs?

Planar graph permanent can be reduced to determinants and so statistics should be amenable.
Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new ...

**2**

votes

**1**answer

52 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

**0**answers

35 views

### Do all induced subgraphs of powers of cycles have a perfect matching

Do all independence induced subgraphs of powers of cycles have a distinct 1-factor? By independence induced, I mean those induced subgraphs which are formed by removing a maximal independent set of ...

**6**

votes

**0**answers

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

**3**

votes

**1**answer

237 views

### Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...