Square-paths and square-cycles in graphs with high minimum degree

Square-paths and square-cycles in graphs with high minimum degree

-
Jan Hladky, Charles University, Prague
Fine Hall 322

We investigate under which minimum-degree condition does a graph G contain a square-path and a square-cycle of a given length. We give precise thresholds, 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 Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms, 9(1-2), 193-211, 1996] concerning containment of a spanning square-path and a spanning square-cycle, respectively. Joint work with P. Allen and J. Bottcher.