An Ore-type condition for large k-factor and disjoint perfect matchings

Win conjectured that a graph $G$ on $n$ vertices contains $k$ disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least $n+k-2$, where $n$ is even and $n\ge k+2$. In this paper, we prove that Win's conjecture is true for $k\ge n∕2$, where $n$ is sufficiently large. To show this result, we prove a theorem on $k$-factor in a graph under some Ore-type condition. Our main tools include Tutte's $k$-factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture.     

A variant of the Erdős-Sós conjecture

A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m-1$ contains every tree with $m$ edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding $m$ and minimum degree at least $\lfloor 2m/3\rfloor$ contains every tree with $m$ edges. As evidence for our conjecture we show (a) for every $m$ there is a $g\left(m\right)$ such that the weakening of the conjecture obtained by replacing the first $m$ by $g\left(m\right)$ holds, and (b) there is a such that the weakening of the conjecture obtained by replacing $\lfloor 2m/3\rfloor$ by $\text{◂⋅▸}\left(1-\gamma \right)m$ holds.