
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