6 papers · 1 filter
On -factors of Hamiltonian graphs
Alberto Espuny DÃaz, António Girão, Bertille Granet +1
Let . We show that, for a sufficiently small , any sufficiently large -vertex Hamiltonian graph of minimum degree at least contains a…
Decomposing cubic graphs into isomorphic linear forests
Gal Kronenberg, Shoham Letzter, Alexey Pokrovskiy +1
A common problem in graph colouring seeks to decompose the edge set of a given graph into few similar and simple subgraphs, under certain divisibility conditions. In 1987 Wormald c…
Shotgun assembly of random graphs
Tom Johnston, Gal Kronenberg, Alexander Roberts +1
In the graph shotgun assembly problem, we are given the balls of radius around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the E…
A note on improved bounds for hypergraph rainbow matching problems
Candida Bowtell, Andrea Freschi, Gal Kronenberg +1
A natural question, inspired by the famous Ryser-Brualdi-Stein Conjecture, is to determine the largest positive integer such that every collection of matchings, each o…
A multidimensional Ramsey Theorem
António Girão, Gal Kronenberg, Alex Scott
Ramsey theory is a central and active branch of combinatorics. Although Ramsey numbers for graphs have been extensively investigated since Ramsey's work in the 1930s, there is stil…
Seymour's second neighbourhood conjecture: random graphs and reductions
Alberto Espuny DÃaz, António Girão, Bertille Granet +1
A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second outneighbourhood is at least as large as its outneighbourhood. In this short…