Zobrazeno 1 - 10
of 53
pro vyhledávání: '"Škorić, Nemanja"'
Let $k \geq 2$ be an integer. Kouider and Lonc proved that the vertex set of every graph $G$ with $n \geq n_0(k)$ vertices and minimum degree at least $n/k$ can be covered by $k - 1$ cycles. Our main result states that for every $\alpha > 0$ and $p =
Externí odkaz:
http://arxiv.org/abs/2003.03311
Since first introduced by Sudakov and Vu in 2008, the study of resilience problems in random graphs received a lot of attention in probabilistic combinatorics. Of particular interest are resilience problems of spanning structures. It is known that fo
Externí odkaz:
http://arxiv.org/abs/1809.07534
A classic result of Erd\H{o}s, Gy\'arf\'as and Pyber states that for every coloring of the edges of $K_n$ with $r$ colors, there is a cover of its vertex set by at most $f(r) = O(r^2 \log r)$ vertex-disjoint monochromatic cycles. In particular, the m
Externí odkaz:
http://arxiv.org/abs/1712.03145
The famous P\'{o}sa-Seymour conjecture, confirmed in 1998 by Koml\'{o}s, S\'{a}rk\"{o}zy, and Szemer\'{e}di, states that for any $k \geq 2$, every graph on $n$ vertices with minimum degree $kn/(k + 1)$ contains the $k$-th power of a Hamilton cycle. W
Externí odkaz:
http://arxiv.org/abs/1709.03901
In 1990 Erd\H{o}s, Faudree, Rousseau and Schelp proved that for $k\geq 2$, every graph with $n\geq k+1$ vertices and $(k-1)(n-k+2)+\binom{k-2}{2}+1$ edges contains a subgraph of minimum degree $k$ on at most $n-\sqrt{n}/\sqrt{6k^3}$ vertices. They co
Externí odkaz:
http://arxiv.org/abs/1703.00273
Publikováno v:
In Journal of Combinatorial Theory, Series B January 2022 152:171-220
Autor:
Nenadov, Rajko, Škorić, Nemanja
Conlon, Gowers, Samotij, and Schacht showed that for a given graph $H$ and a constant $\gamma > 0$, there exists $C > 0$ such that if $p \ge Cn^{-1/m_2(H)}$ then asymptotically almost surely every spanning subgraph $G$ of the random graph $\mathcal{G
Externí odkaz:
http://arxiv.org/abs/1611.09466
We consider collaborative graph exploration with a set of $k$ agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other vertices. We assume agents are deterministic, vertices are distinguishabl
Externí odkaz:
http://arxiv.org/abs/1610.01753
Autor:
Gugelmann, Luca, Nenadov, Rajko, Person, Yury, Škorić, Nemanja, Steger, Angelika, Thomas, Henning
A celebrated result of R\"odl and Ruci\'nski states that for every graph $F$, which is not a forest of stars and paths of length $3$, and fixed number of colours $r\ge 2$ there exist positive constants $c, C$ such that for $p \leq cn^{-1/m_2(F)}$ the
Externí odkaz:
http://arxiv.org/abs/1610.00935
A classic result of Erd\H{o}s and P\'osa says that any graph contains either $k$ vertex-disjoint cycles or can be made acyclic by deleting at most $O(k \log k)$ vertices. Here we generalize this result by showing that for all numbers $k$ and $l$ and
Externí odkaz:
http://arxiv.org/abs/1603.07588