اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Rainbow Turan number of paths
150
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $F$ be a fixed graph. The rainbow Turan number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstraete. In this paper, we show that the rainbow Turan number of a path with $k+1$ edges is less than $left(frac{9k}{7}+2right) n$, improving an earlier estimate of Johnston, Palmer and Sarkar.
قيم البحث
اقرأ أيضاً
For a fixed graph $F$ and an integer $t$, the dfn{rainbow saturation number} of $F$, denoted by $sat_t(n,mathfrak{R}(F))$, is defined as the minimum number of edges in a $t$-edge-colored graph on $n$ vertices which does not contain a dfn{rainbow copy
} of $F$, i.e., a copy of $F$ all of whose edges receive a different color, but the addition of any missing edge in any color from $[t]$ creates such a rainbow copy. Barrus, Ferrara, Vardenbussche and Wenger prove that $sat_t(n,mathfrak{R}(P_ell))ge n-1$ for $ellge 4$ and $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell-1} rceil cdot binom{ell-1}{2}$ for $tge binom{ell-1}{2}$, where $P_ell$ is a path with $ell$ edges. In this short note, we improve the upper bounds and show that $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell} rceil cdot left({{ell-2}choose {2}}+4right)$ for $ellge 5$ and $tge 2ell-5$.
The Turan number of a graph $H$, denoted by $ex(n,H)$, is the maximum number of edges in any graph on $n$ vertices which does not contain $H$ as a subgraph. Let $P_{k}$ denote the path on $k$ vertices and let $mP_{k}$ denote $m$ disjoint copies of $P
_{k}$. Bushaw and Kettle [Tur{a}n numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20(2011) 837--853] determined the exact value of $ex(n,kP_ell)$ for large values of $n$. Yuan and Zhang [The Tur{a}n number of disjoint copies of paths, Discrete Math. 340(2)(2017) 132--139] completely determined the value of $ex(n,kP_3)$ for all $n$, and also determined $ex(n,F_m)$, where $F_m$ is the disjoint union of $m$ paths containing at most one odd path. They also determined the exact value of $ex(n,P_3cup P_{2ell+1})$ for $ngeq 2ell+4$. Recently, Bielak and Kieliszek [The Tur{a}n number of the graph $2P_5$, Discuss. Math. Graph Theory 36(2016) 683--694], Yuan and Zhang [Tur{a}n numbers for disjoint paths, arXiv: 1611.00981v1] independently determined the exact value of $ex(n,2P_5)$. In this paper, we show that $ex(n,2P_{7})=max{[n,14,7],5n-14}$ for all $n ge 14$, where $[n,14,7]=(5n+91+r(r-6))/2$, $n-13equiv r,(text{mod }6)$ and $0leq r< 6$.
Let $F$ be a graph. The planar Turan number of $F$, denoted by $text{ex}_{mathcal{P}}(n,F)$, is the maximum number of edges in an $n$-vertex planar graph containing no copy of $F$ as a subgraph. Let $Theta_k$ denote the family of Theta graphs on $kge
q 4$ vertices, that is, a graph obtained by joining a pair of non-consecutive vertices of a $k$-cycle with an edge. Y. Lan, et.al. determined sharp upper bound for $text{ex}_{mathcal{P}}(n,Theta_4)$ and $text{ex}_{mathcal{P}}(n,Theta_5)$. Moreover, they obtained an upper bound for $text{ex}_{mathcal{P}}(n,Theta_6)$. They proved that, $text{ex}_{mathcal{P}}(n,Theta_6)leq frac{18}{7}n-frac{36}{7}$. In this paper, we improve their result by giving a bound which is sharp. In particular, we prove that $text{ex}_{mathcal{P}}(n,Theta_6)leq frac{18}{7}n-frac{48}{7}$ and demonstrate that there are infinitely many $n$ for which there exists a $Theta_6$-free planar graph $G$ on $n$ vertices, which attains the bound.
For a graph $H$ consisting of finitely many internally disjoint paths connecting two vertices, with possibly distinct lengths, we estimate the corresponding extremal number $text{ex}(n,H)$. When the lengths of all paths have the same parity, $text{ex
}(n,H)$ is $O(n^{1+1/k^ast})$, where $2k^ast$ is the size of the smallest cycle which is included in $H$ as a subgraph. We also establish the matching lower bound in the particular case of $text{ex}(n,Theta_{3,5,5})$, where $Theta_{3,5,5}$ is the graph consisting of three disjoint paths of lengths $3,5$ and $5$ connecting two vertices.
Let ${rm ex}_{mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${rm ex}_{mathcal{P}}(n,T,H)$ is the well studied function, the planar Turan number of
$H$, denoted by ${rm ex}_{mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${rm ex}_{mathcal{P}}(n,C_4)$ and ${rm ex}_{mathcal{P}}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${rm ex}_{mathcal{P}}(n,C_6)leq frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${rm ex}_{mathcal{P}}(n,C_6) leq frac{5}{2}n-7$, for all $ngeq 18$, which improves Lans result. We also pose a conjecture on ${rm ex}_{mathcal{P}}(n,C_k)$, for $kgeq 7$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
