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.     

Extending regular edge-colorings of complete hypergraphs

A coloring (partition) of the collection $(\genfrac{}{}{0.0pt}{}{X}{h})$ of all $h$-subsets of a set $X$ is $r$-regular if the number of times each element of $X$ appears in each color class (all sets of the same color) is the same number $r$. We are interested in finding the conditions under which a given $r$-regular coloring of $(\genfrac{}{}{0.0pt}{}{X}{h})$ is extendible to an $s$-regular coloring of $(\genfrac{}{}{0.0pt}{}{Y}{h})$ for $s⩾r$ and $Y⊋X$. The case $\text{◂,▸}h=2,r=s=1$ was solved by Cruse, and due to its connection to completing partial symmetric latin squares, many related problems are extensively studied in the literature, but very little is known for $h⩾3$. The case $r=s=1$ was solved by Häggkvist and Hellgren, settling a conjecture of Brouwer and Baranyai. The cases $h=2$ and $h=3$ were solved by Rodger and Wantland, and Bahmanian and Newman, respectively. In this paper, we completely settle the cases $h=4,\text{◂⩾▸}|Y|⩾4|X|$ and $h=5,\text{◂⩾▸}|Y|⩾5|X|$.