1 citations · 2 across the 11 of their papers we have counts for
5 papers · 1 filter
On decomposition thresholds for odd-length cycles and other tripartite graphs
Darryn Bryant, Peter Dukes, Daniel Horsley +2
An (edge) decomposition of a graph is a set of subgraphs of whose edge sets partition the edge set of . Here we show, for each odd , that any graph of s…
Regular subgraphs at every density
Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1
In 1975, Erdős and Sauer asked to estimate, for any constant , the maximum number of edges an -vertex graph can have without containing an -regular subgraph. In a recent b…
Approximate path decompositions of regular graphs
Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy +1
We show that the edges of any -regular graph can be almost decomposed into paths of length roughly , giving an approximate solution to a problem of Kotzig from 1957. Along th…
Edge-disjoint cycles with the same vertex set
Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1
In 1975, Erdős asked for the maximum number of edges that an -vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turá…
Hamiltonicity of expanders: optimal bounds and applications
Nemanja Draganić, Richard Montgomery, David Munhá Correia +2
An -vertex graph is a -expander if for every with and there is an edge between every two disjoint sets of at least …