Department of
Applied
Mathematics

Schelp's conjecture

Diana Piguet

Abstract

It is conjectured that for any edge-coloring of the complete graph K_{2n-2} by two colors, one of the colors is T_n-universal, i.e. it contains any tree on n vertices. This is known for large values of n. Inspired by this conjecture, R. Schelp asked whether we may delete many edges of K_{2n-2} without loosing the property that one of the color classes is T_n-universal and conjectured the following.

Conjecture (Schelp): For any edge-coloring of K_{t,t,t} by two colors, one of the color classes is universal with respect to the trees of order 3t/2-o(t) with bounded degree.

We prove this conjecture using the Regularity Lemma. This is a joint work with Julia Boettcher and Jan Hladky.