Abstract. Kőnig’s theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of Kőnig’s theorem is that in every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic components needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text]. We prove the following strengthening of Kőnig’s theorem: In every 2-coloring of the edges of a graph [Formula: see text], the number of monochromatic subgraphs of bounded diameter needed to cover the vertex set of [Formula: see text] is at most the independence number of [Formula: see text].

Let $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $\vec{T}_4$'s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $\vec{T}_k$'s.

A branch vertex in a tree is a vertex of degree at least three. We prove that, for all $s\geq 1$, every connected graph on $n$ vertices with minimum degree at least $(\frac{1}{s+3}+o(1))n$ contains a spanning tree having at most $s$ branch vertices. Asymptotically, this is best possible and solves a problem of Flandrin, Kaiser, Kuz̆el, Li, and Ryjác̆ek, which was originally motivated by an optimization problem in the design of optical networks.

Let $n$ be sufficiently large and suppose that $G$ is a digraph on $n$ vertices where every vertex has in- and outdegree at least $n/2$. We show that $G$ contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is $n/2+1$. Our result is best possible and improves on an approximate result by Häggkvist and Thomason.

Bipartite graph tiling was studied by Zhao [SIAM J. Discrete Math., 23 (2009), pp. 888–900], who gave the best possible minimum degree conditions for a balanced bipartite graph on $2ms$ vertices to contain m vertex disjoint copies of $K_{s,s}$. Let $s 2s+1$. We give the best possible minimum degree condition in this case.

Let G and H be balanced $U,V$-bigraphs on $2n$ vertices with $\Delta(H)\leq2$. Let k be the number of components of H, $\delta_U:=\min\{\deg_G(u):u\in U\}$ and $\delta_V:=\min\{\deg_G(v):v\in V\}$. We prove that if n is sufficiently large and $\delta_U+\delta_V\geq n+k$, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when $\delta_U+\delta_V\geq n+2$ as long as n is sufficiently large in terms of k and $\delta(G)\geq\frac{n}{200k}+1$.