UVictoria Discrete Math Seminar: Shannon Ogden

The question of whether one graph can be embedded in another is a fundamental problem in graph theory. In 2020, Joos and Kim introduced a generalization of the basic graph embedding problem to graph collections. Let $G=\{G_1,\ldots,G_m\}$ be a collection of not necessarily distinct graphs on a common vertex set V with $|V|=n$. Given a graph H with at most m edges, a rainbow copy of H in G is a copy of H on V using at most one edge from each graph G_i. Joos and Kim showed that Dirac's Theorem can be generalized to this setting; that is, if m=n and the minimum degree of each graph in G is at least n/2, then G contains a rainbow Hamilton cycle. Recently, Bowtell, Morris, Pehova, and Staden proved an asymptotically best possible strengthening of this result when we instead require the existence of Hamilton cycles with every possible edge-colouring. We prove a version of their result for powers of Hamilton cycles. Based on work with Emily Heath, Joseph Hyde, and Natasha Morrison.