3 papers
math.CO2026
Semidegree threshold for spanning trees in oriented graphs
Pedro Araújo, Pedro Araújo, Giovanne Santos +1
We show that for all and , there is some such that, if , then every oriented graph on vertices with minimum semidegree at least $(3/8…
math.CO2025
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\…
math.CO2025
A bounded diameter strengthening of KÅnig's Theorem
Louis DeBiasio, António Girão, Penny Haxell +1
K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at mos…