Bruce Reed

activity

20242026

collaborators

Showing math.COShow all

6 papers · 1 filter

math.CO2026

The Erd\H os-Sós conjecture in dense graphs

Bruce Reed, Maya Stein

The Erd\H os--Sós conjecture states that every $n$ -vertex graph with more than $(k - 2) n /2$ edges contains every $k$ -vertex tree. We prove that for every $γ$ there is an $n_{0}$ such t…

math.CO2026

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 $n$ -vertex graph $G$ with more than $(k - 2) n /2$ edges contains every $k$ -vertex tree. We solve the extremal cases of this conjecture,…

math.CO2025

The asymptotic $χ$ -boundedness of hereditary families

Bruce Reed, Yelena Yuditsky

A family $F$ of graphs is asymptotically $χ$ -bounded with bounding function $f$ if almost every graph $G$ in the family satisfies $χ (G) \leq f (ω (G))$ . A graph is $H$ -free if…

math.CO2025

Typical $T$ -free graphs

Bruce Reed, Yelena Yuditsky

We prove that for every tree $T$ which is not an edge, for almost every graph $G$ which does not contain $T$ as an induced subgraph, $V (G)$ has a partition into $α (T) - 1$ parts cert…

math.CO2024

Embedding Nearly Spanning Trees

Bruce Reed, Maya Stein

The Erdős-Sós Conjecture states that every graph with average degree exceeding $k - 1$ contains every tree with $k$ edges as a subgraph. We prove that there are $δ > 0$ and $k_0\in\mat…

math.CO2024

Vertex Ranking of Degenerate Graphs

John Iacono, Piotr Micek, Pat Morin +1

An $ℓ$ -vertex-ranking of a graph $G$ is a colouring of the vertices of $G$ with integer colours so that in any connected subgraph $H$ of $G$ with diameter at most $ℓ$ , there…

The Erd\H os-Sós conjecture in dense graphs

The extremal cases of the Erd\H os--Sós conjecture

The asymptotic χ-boundedness of hereditary families

Typical T-free graphs

Embedding Nearly Spanning Trees

Vertex Ranking of Degenerate Graphs

The asymptotic $χ$ -boundedness of hereditary families

Typical $T$ -free graphs