The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint directed cycles. Despite being posed in 1981, this conjecture remains unresolved for all $k \ge 4$. We prove a relaxation of this conjecture: every digraph $D$ of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint cycles, each of which either is directed or can be made directed by reversing one of its arcs. This bound is sharp and answers a question raised by Cames van Batenburg during the online workshop"Entropy Compression and Related Methods"in $2021$.
The Bermond--Thomassen Conjecture asserts that every digraph with minimum out-degree at least $2k-1$ contains $k$ disjoint directed cycles; it remains open in general. We asymptotically resolve it: there exist an absolute constant $K$ and a function $g(k)=o(k)$, independent of $n$, such that every $n$-vertex finite sim...
Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $\Omega(k^{8/11})$ bound for this conjecture, improving upon the $\Omega(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement...
Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of orde...
Let $G$ be a Borel digraph with maximum out-degree $d \in \mathbb{N}$. We show that $G$ admits a random Borel $(2d+1)$-coloring for which every edge is almost surely not monochromatic. This gives a simpler proof of a recent result of Pelayo-G\'omez: such a graph $G$ admits a measurable proper $(2d+1)$-coloring with res...
Anton Bernshteyn, Edward Hou, Forte Shinko et al.· 0 citations
A graph $G$ is called $F$-irregular if all its vertices have distinct $F$-degrees, defined as the number of subgraphs of $G$ isomorphic to a given graph $F$ and containing the respective vertex. We prove the Strong Conjecture about $F$-irregular graphs (Dovzhenok, Filuta, and Chuhai, 2024), which states that for every...
For every integer $k\ge2$, Chen and Raspaud conjectured that each graph $G$ with odd girth $\og(G)\ge2k+1$ and maximum average degree $\mad(G)<2+1/k$ has a $(2k+1:k)$-coloring. In this paper, we prove the conjecture.
Qi Wu, Yong Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
