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

74
questions

**0**

votes

**1**answer

58 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

78 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

19 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

51 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

130 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

26 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

267 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

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

**17**

votes

**1**answer

722 views

### Vertex Coloring inherited from Perfect Matchings (motivated by Quantum Physics)

The following purely graph-theoretic question is motivated by quantum mechanics (and a special case of the questions asked here).
Bi-Colored Graph: A bi-colored weighted graph $G=(V(G),E(G))$, on $n$ ...

**2**

votes

**1**answer

45 views

### Triangle Center from Weighted Perfect Matchings

let $\Delta$ be the triangle whose corners $A$, $B$, $C$ points in general position in Euclidean plane and, let $D$ be a fourth point inside $\Delta$.
Question:
what is known about the ...

**0**

votes

**0**answers

14 views

### Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching

This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices.
A simple heuristical requirement for such a bicoloring could be ...