On the Loebl-Komlós-Sós Conjecture, Lopsided Trees, and Certain Caterpillars

Abstract

Let $G$ be a graph with at least half of the vertices having degree at least $k$. For a tree $T$ with $k$ edges, Loebl, Komlós, and Sós conjectured that $G$ contains $T$. It is known that if the length of a longest path in $T$ (i.e., the diameter of $T$) is at most 5, then $G$ contains $T$. Since $T$ is a bipartite graph, let $\ell$ be the number of vertices in the smaller (or equal) part. Clearly $1\le \ell \le \frac{1}{2}(k+1)$. In our main theorem, we prove that if $1\le \ell \le \frac{1}{6}k+1$, then the graph $G$ contains $T$. Notice that this includes certain trees of diameter up to $\frac{1}{3}k+2$.

If a tree $T$ consists of only a path and vertices that are connected to the path by an edge, then the tree $T$ is a caterpillar. Let $P$ be the path obtained from the caterpillar $T$ by removing each leaf of $T$, where $P=a_1,\dots ,a_r$. The path $P$ is the spine of the caterpillar $T$, and each vertex on the spine of $T$ with degree at least 3 in $T$ is a joint. It is known that the graph $G$ contains certain caterpillars having at most two joints. If only odd-indexed vertices on the spine $P$ are joints, then the caterpillar $T$ is an odd caterpillar. If the spine $P$ has at most $\lceil \frac{1}{2}k\rceil$ vertices, then $T$ is a short caterpillar. We prove that the graph $G$ contains every short, odd caterpillar with $k$ edges.