Abstract by
Tao Jiang
Trees in graphs with large girth.
Dobson (1994) conjectured that every graph $G$ with girth at least $2t+1$ and minimum degree at least $k/t$ contains every tree $T$ with $k$ edges whose maximum degree is at most the minimum degree of $G$.

The conjecture has been proved for $t\le 3$. A slightly stronger version for $t=2$, proved by Brandt and Dobson, implies the famous
Erdos-Sos Conjecture for graphs with girth at least 5. The Erdos-Sos Conjecture states that every graph on $n$ vertices with more than
$n(k-1)/2$ edges contains every tree with $k$ edges.

In this talk, we prove Dobson's conjecture.


Tuesday, September 07, 1999, 12:00 p.m.  - 241 Altgeld Hall
GRAPH THEORY

Go Back