Embedding thin large graphs

Jan Hladký

Abstract

We investigate under which minimum-degree condition does a graph $G$ contain a square-path and a square-cycle of a certain length. We give precise tresholds, assuming that the order of $G$ is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B, 67(2), 167-182, 1996] and of Koml\'os, Sark\"ozy, and Szemer\'edi [Random Structures Algorithms, 9(1-2), 193-211, 1996] concerning containment of a spanning square-path and a spanning square-cycle, respectively.

The method also yields optimal minimum-degree threshold for the problem of embedding a three-colorable graph $H$ of bounded maximum degree and sublinear bandwidth in the case that the order $H$ is of the same order as the order of the hosting graph $G$. This can be thought of as a version of the Bollob\'as-Koml\'os Conjecture, solved recently by B\"ottcher, Schacht and Taraz [J. Combin. Theory Ser. B, 98(4), 752-777, 2008], [Math. Ann, 343(1),