Zobrazeno 1 - 10
of 210
pro vyhledávání: '"Böttcher, Julia"'
Given a family $\mathcal{H}$ of graphs, a graph $G$ is called $\mathcal{H}$-universal if $G$ contains every graph of $\mathcal{H}$ as a subgraph. Following the extensive research on universal graphs of small size for bounded-degree graphs, Alon asked
Externí odkaz:
http://arxiv.org/abs/2309.05468
Answering a question by Letzter and Snyder, we prove that for large enough $k$ any $n$-vertex graph $G$ with minimum degree at least $\frac{1}{2k-1}n$ and without odd cycles of length less than $2k+1$ is $3$-colourable. In fact, we prove a stronger r
Externí odkaz:
http://arxiv.org/abs/2302.01875
Autor:
Allen, Peter, Böttcher, Julia
We prove asymptotically optimal bounds on the number of edges a graph $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $D$-degenerate graph on $n$ vertices with bounded maximum degree. We also improve th
Externí odkaz:
http://arxiv.org/abs/2211.15819
Autor:
Allen, Peter, Böttcher, Julia, Corsten, Jan, Davies, Ewan, Jenssen, Matthew, Morris, Patrick, Roberts, Barnaby, Skokan, Jozef
For a graph $G$ and $p\in[0,1]$, we denote by $G_p$ the random sparsification of $G$ obtained by keeping each edge of $G$ independently, with probability $p$. We show that there exists a $C>0$ such that if $p\geq C(\log n)^{1/3}n^{-2/3}$ and $G$ is a
Externí odkaz:
http://arxiv.org/abs/2209.01116
Partitioning a 2-edge-coloured graph of minimum degree $2n/3 + o(n)$ into three monochromatic cycles
Lehel conjectured in the 1970s that every red and blue edge-coloured complete graph can be partitioned into two monochromatic cycles. This was confirmed in 2010 by Bessy and Thomass\'e. However, the host graph $G$ does not have to be complete. It it
Externí odkaz:
http://arxiv.org/abs/2204.00496
Publikováno v:
In European Journal of Combinatorics October 2024 121
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $\alpha \in (0,1)$, the union of any $n$-vertex graph with minimum degree $\alpha n$ and the binomial random graph $G(n,p
Externí odkaz:
http://arxiv.org/abs/2202.05215
We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,\dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/\log n$, then $\{T_1,\dots,T_n\}$ packs into $K_n$. Our main result actually allow
Externí odkaz:
http://arxiv.org/abs/2106.11720
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ and the binomial random graph $G(n,p)$. For $\ell \g
Externí odkaz:
http://arxiv.org/abs/2103.06136
We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$-vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$. We prove that
Externí odkaz:
http://arxiv.org/abs/2011.07612