اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn Approximate Version of the Strong Nine Dragon Tree Conjecture
119
0
0.0
(
0
)
تأليف
Benjamin Moore
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Strong Nine Dragon Tree Conjecture asserts that for any integers $k$ and $d$ any graph with fractional arboricity at most $k + frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that for at least one of the forests, every connected component contains at most $d$ edges. We prove this conjecture when $d leq k+1$. We also prove an approximate version of this conjecture, that is, we prove that for any positive integers $k$ and $d$, any graph with fractional arboricity at most $k + frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that one for at least one of the forests, every connected component contains at most $d + frac{d(k (2lceil frac{d}{k+1} +2 rceil)^{lceil frac{d}{k+1} + 2) rceil} - k)}{k+1} $ edges.
قيم البحث
اقرأ أيضاً
We prove that for any positive integers $k$ and $d$, if a graph $G$ has maximum average degree at most $2k + frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests $C_{1},ldots,C_{k+1}$ such that there is an $i$ such that for every connected
component $C$ of $C_{i}$, we have that $e(C) leq d$.
We prove that for any $varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(frac32-varepsilon)t$-colouring that is frozen with respect to Kempe changes, i.e. any two colour classes induce a connected
component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.
We say that the families $mathcal F_1,ldots, mathcal F_{s+1}$ of $k$-element subsets of $[n]$ are cross-dependent if there are no pairwise disjoint sets $F_1,ldots, F_{s+1}$, where $F_iin mathcal F_i$ for each $i$. The rainbow version of the ErdH os
Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that $min_{i} |mathcal F_i|le maxbig{{nchoose k}-{n-schoose k}, {(s+1)k-1choose k}big}$. In this paper, we prove this conjecture for $n>3e(s+1)k$ and $s>10^7$. One of the main tools in the proof is a concentration inequality due to Frankl and the author.
Loebl, Komlos, and Sos conjectured that any graph with at least half of its vertices of degree at least k contains every tree with at most k edges. We propose a version of this conjecture for skewed trees, i.e., we consider the class of trees with at
most k edges such that the sizes of the colour classes of the trees have a given ratio. We show that our conjecture is asymptotically correct for dense graphs. The proof relies on the regularity method. Our result implies bounds on Ramsey number of several trees of given skew.
We prove that any quasirandom graph with $n$ vertices and $rn$ edges can be decomposed into $n$ copies of any fixed tree with $r$ edges. The case of decomposing a complete graph establishes a conjecture of Ringel from 1963.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
