5 citations · 9 across the 19 of their papers we have counts for
23 papers · 1 filter
The Lovász conjecture holds for moderately dense Cayley graphs
Benjamin Bedert, Nemanja Draganić, Alp Müyesser +1
We show that there is an absolute constant such that every large connected -vertex Cayley graph with degree has a Hamilton cycle. This makes progress towar…
Cycles with almost linearly many chords
Nemanja Draganić, António Girão
We prove that constant minimum degree already forces cycles with almost linearly many chords. Specifically, every graph with contains a cycle of length …
On Independent Spanning Trees in Random and Pseudorandom Graphs
Nemanja Draganić, Keith Frankston, Michael Krivelevich +2
In 1989, Zehavi and Itai conjectured that every -connected graph contains independent spanning trees rooted at any prescribed vertex . That is, for each vertex , the u…
Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
Nemanja Draganić, Jaehoon Kim, Hyunwoo Lee +3
Dirac's classical theorem asserts that, for , any -vertex graph with minimum degree at least is Hamiltonian. Furthermore, if we additionally assume that such grap…
New bounds for linear arboricity and related problems
Micha Christoph, Nemanja Draganić, António Girão +3
A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree can be decomposed into at most $\lceil(Δ+1)…
Cyclic subsets in regular Dirac graphs
Nemanja Draganić, Peter Keevash, Alp Müyesser
In 1996, in his last paper, Erdős asked the following question that he formulated together with Faudree: is there a positive such that any -regular graph on ver…
Pósa rotation through a random permutation
Nemanja Draganić, Peter Keevash
What minimum degree of a graph on vertices guarantees that the union of and a random -factor (or permutation) is with high probability Hamiltonian? Girão and Espuny…
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 …
Long induced paths in expanders
Nemanja Draganić, Peter Keevash
We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, s…
Optimal Hamilton covers and linear arboricity for random graphs
Nemanja Draganić, Stefan Glock, David Munhá Correia +1
In his seminal 1976 paper, Pósa showed that for all , the binomial random graph is with high probability Hamiltonian. This leads to the following natural…
Size-Ramsey numbers of structurally sparse graphs
Nemanja Draganić, Marc Kaufmann, David Munhá Correia +2
Size-Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erdős, Faudree, Rousseau and Schelp in 1978. Research has mainly…
A generalization of Bondy's pancyclicity theorem
Nemanja Draganić, David Munhá Correia, Benny Sudakov
The bipartite independence number of a graph , denoted as , is the minimal number such that there exist positive integers and with with the pro…
Chvátal-Erdős condition for pancyclicity
Nemanja Draganić, David Munhá Correia, Benny Sudakov
An -vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from up to . A celebrated…
Pancyclicity of Hamiltonian graphs
Nemanja Draganić, David Munhá Correia, Benny Sudakov
An -vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices, and it is pancyclic if it contains cycles of all lengths from up to . In 1972, Erd…
Tight bounds for divisible subdivisions
Shagnik Das, Nemanja Draganić, Raphael Steiner
Alon and Krivelevich proved that for every -vertex subcubic graph and every integer there exists a (smallest) integer such that every -minor contai…
Ramsey number of 1-subdivisions of transitive tournaments
Nemanja Draganić, David Munhá Correia, Benny Sudakov +1
The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided…
Short proofs for long induced paths
Nemanja Draganić, Stefan Glock, Michael Krivelevich
We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the ind…
Unavoidable hypergraphs
M. Bucić, N. Draganić, B. Sudakov +1
The following very natural problem was raised by Chung and Erdős in the early 80's and has since been repeated a number of times. What is the minimum of the Turán number $\text{ex}…
A Note on Powers of Paths in Tournaments
Nemanja Draganić, David Munhá Correia, Benny Sudakov
In this note we show that every tournament on vertices contains the -th power of a directed path of length , which improves upon the recent bound of Scott and Ko…
Powers of paths in tournaments
Nemanja Draganić, François Dross, Jacob Fox +7
In this short note we prove that every tournament contains the -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also g…
Large induced trees in dense random graphs
Nemanja Draganić
Erdős and Palka initiated the study of the maximal size of induced trees in random graphs in 1983. They proved that for every fixed the size of a largest induced tree in $G…
Large induced matchings in random graphs
Oliver Cooley, Nemanja Draganić, Mihyun Kang +1
Given a large graph , does the binomial random graph contain a copy of as an induced subgraph with high probability? This classical question has been studied extens…
Universal and unavoidable graphs
Matija Bucić, Nemanja Draganić, Benny Sudakov
The Turán number of a graph is the maximal number of edges in an -free graph on vertices. In Chung and Erdős asked which graphs with edge…