Search for: All records

Abstract For a subgraph$$G$$of the blow-up of a graph$$F$$, we let$$\delta ^*(G)$$be the smallest minimum degree over all of the bipartite subgraphs of$$G$$induced by pairs of parts that correspond to edges of$$F$$. Johansson proved that if$$G$$is a spanning subgraph of the blow-up of$$C_3$$with parts of size$$n$$and$$\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$$, then$$G$$contains$$n$$vertex disjoint triangles, and presented the following conjecture of Häggkvist. If$$G$$is a spanning subgraph of the blow-up of$$C_k$$with parts of size$$n$$and$$\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$$, then$$G$$contains$$n$$vertex disjoint copies of$$C_k$$such that each$$C_k$$intersects each of the$$k$$parts exactly once. A similar conjecture was also made by Fischer and the case$$k=3$$was proved for large$$n$$by Magyar and Martin. In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of$$G$$to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically. 

Both Cuckler and Yuster independently conjectured that when $$n$$ is an odd positive multiple of $$3$$ every regular tournament on $$n$$ vertices contains a collection of $n/3$$ vertex-disjoint copies of the cyclic triangle. Soon after, Keevash \& Sudakov proved that if $$G$$ is an orientation of a graph on $$n$$ vertices in which every vertex has both indegree and outdegree at least $(1/2 - o(1))n$, then there exists a collection of vertex-disjoint cyclic triangles that covers all but at most $$3$$ vertices. In this paper, we resolve the conjecture of Cuckler and Yuster for sufficiently large $$n$$.