# All Questions

Tagged with graph-theory perfect-matchings

55
questions

**0**

votes

**0**answers

34 views

### Algorithmic complexity of deciding the existence of regular $\mathrm{f}$-factors in graphs

Finding regular $\mathrm{f}$-factors in undirected simple graphs can be reduced to finding a perfect matching by utilizing the gadgets of Tutte or of Lovász and Plummer; there are several algorithms ...

**0**

votes

**1**answer

57 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

171 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

65 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

90 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

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

**1**

vote

**1**answer

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

**2**

votes

**1**answer

55 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

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

**20**

votes

**1**answer

973 views

### Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (24.08.2019): As I consider this question important for quantum physics, I have announced a 3000 Euro award on its solution, see here for more details.
Added (19.09.2019): This problem can be ...

**7**

votes

**1**answer

187 views

### Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?

The sequence A006318 at OEIS stands for the Schr?der numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...

**2**

votes

**0**answers

33 views

### Can Orientability of Manifolds be Generalized to TSP Instances?

It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular ...

**6**

votes

**1**answer

109 views

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...

**11**

votes

**1**answer

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