ترغب بنشر مسار تعليمي؟ اضغط هنا

Transversal $C_k$-factors in subgraphs of the balanced blow-up of $C_k$

109   0   0.0 ( 0 )
 نشر من قبل Theodore Molla
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

For a subgraph $G$ of the blow-up of a graph $F$, we let $delta^*(G)$ be the smallest minimum degree over all of the bipartite subgraphs of $G$ induced by pairs of parts that correspond to edges of $F$. In [Triangle-factors in a balanced blown-up triangle. Discrete Mathematics, 2000], Johansson proved that if $G$ is a spanning subgraph of the blow-up of $C_3$ with parts of size $n$ and $delta^*(G) ge frac{2}{3}n + sqrt{n}$, then $G$ contains $n$ vertex-disjoint triangles, and presented the following conjecture of Haggkvist: If $G$ is a spanning subgraph of the blow-up of $C_k$ with parts of size $n$ and $delta^*(G) ge (1 + 1/k)n/2 + 1$, then $G$ contains $n$ vertex disjoint copies of $C_k$ such that each $C_k$ intersects each of the $k$ parts exactly once. The degree condition of this conjecture is tight when $k=3$ and cannot be strengthened by more than one when $k ge 4$., A similar conjecture was also made by Fischer in [Variants of the Hajnal-Szemeredi Theorem. Journal of Graph Theory, 1999] and the triangle case was proved for large $n$ by Magyar and Martin in [Tripartite version of the Corradi-Hajnal Theorem. Discrete Mathematics, 2002]. In this paper, we prove this Conjecture asymptotically. We also pose a conjecture which generalizes this result by allowing the minimum degree conditions on the nonempty bipartite subgraphs induced by pairs of parts to vary. Our second result supports this new conjecture by proving the triangle case. This result generalizes Johannsons result asymptotically.

قيم البحث

اقرأ أيضاً

We show that for $n geq 3, n e 5$, in any partition of $mathcal{P}(n)$, the set of all subsets of $[n]={1,2,dots,n}$, into $2^{n-2}-1$ parts, some part must contain a triangle --- three different subsets $A,B,Csubseteq [n]$ such that $Acap B$, $Acap C$, and $Bcap C$ have distinct representatives. This is sharp, since by placing two complementary pairs of sets into each partition class, we have a partition into $2^{n-2}$ triangle-free parts. We also address a more general Ramsey-type problem: for a given graph $G$, find (estimate) $f(n,G)$, the smallest number of colors needed for a coloring of $mathcal{P}(n)$, such that no color class contains a Berge-$G$ subhypergraph. We give an upper bound for $f(n,G)$ for any connected graph $G$ which is asymptotically sharp (for fixed $k$) when $G=C_k, P_k, S_k$, a cycle, path, or star with $k$ edges. Additional bounds are given for $G=C_4$ and $G=S_3$.
Given a collection of graphs $mathbf{G}=(G_1, ldots, G_m)$ with the same vertex set, an $m$-edge graph $Hsubset cup_{iin [m]}G_i$ is a transversal if there is a bijection $phi:E(H)to [m]$ such that $ein E(G_{phi(e)})$ for each $ein E(H)$. We give asy mptotically-tight minimum degree conditions for a graph collection on an $n$-vertex set to have a transversal which is a copy of a graph $H$, when $H$ is an $n$-vertex graph which is an $F$-factor or a tree with maximum degree $o(n/log n)$.
193 - Taras Banakh , Leijie Wang 2019
We prove that for a stratifiable scattered space $X$ of finite scattered height, the function space $C_k(X)$ endowed with the compact-open topology is Baire if and only if $X$ has the Moving Off Property of Gruenhage and Ma. As a byproduct of the pro of we establish many interesting Baire category properties of the function spaces $C_k(X,Y)={fin C_k(X,Y):f(X)subset{*_Y}}$, where $X$ is a topological space, $X$ is the set of non-isolated points of $X$, and $Y$ is a topological space with a distinguished point $*_Y$.
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three spar
87 - Franklin D. Tall 2015
We prove some consistency results concerning the Moving Off Property for locally compact spaces and thus the question of whether their function spaces are Baire.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا