Menu
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 \leq \ell \leq \frac{1}{2}(k + 1) \). In our main theorem, we prove that if \( 1 \leq \ell \leq \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, \ldots, 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.