7 papers
The Erd\H os-Sós conjecture in dense graphs
Bruce Reed, Maya Stein
The Erd\H os--Sós conjecture states that every -vertex graph with more than edges contains every -vertex tree. We prove that for every there is an such t…
The extremal cases of the Erd\H os--Sós conjecture
Bruce Reed, Maya Stein
The Erd\H os--Sós conjecture states that every -vertex graph with more than edges contains every -vertex tree. We solve the extremal cases of this conjecture,…
The asymptotic -boundedness of hereditary families
Bruce Reed, Yelena Yuditsky
A family of graphs is asymptotically -bounded with bounding function if almost every graph in the family satisfies . A graph is -free if…
Typical -free graphs
Bruce Reed, Yelena Yuditsky
We prove that for every tree which is not an edge, for almost every graph which does not contain as an induced subgraph, has a partition into parts cert…
Embedding Nearly Spanning Trees
Bruce Reed, Maya Stein
The Erdős-Sós Conjecture states that every graph with average degree exceeding contains every tree with edges as a subgraph. We prove that there are and $k_0\in\mat…
Vertex Ranking of Degenerate Graphs
John Iacono, Piotr Micek, Pat Morin +1
An -vertex-ranking of a graph is a colouring of the vertices of with integer colours so that in any connected subgraph of with diameter at most , there…
Linear bounds on treewidth in terms of excluded planar minors
J. Pascal Gollin, Kevin Hendrey, Sang-il Oum +1
One of the fundamental results in graph minor theory is that for every planar graph , there is a minimum integer such that graphs with no minor isomorphic to have tre…