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

On Edge-Colored Saturation Problems

66   0   0.0 ( 0 )
 نشر من قبل Michael Tait
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




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

Let $mathcal{C}$ be a family of edge-colored graphs. A $t$-edge colored graph $G$ is $(mathcal{C}, t)$-saturated if $G$ does not contain any graph in $mathcal{C}$ but the addition of any edge in any color in $[t]$ creates a copy of some graph in $mathcal{C}$. Similarly to classical saturation functions, define $mathrm{sat}_t(n, mathcal{C})$ to be the minimum number of edges in a $(mathcal{C},t)$ saturated graph. Let $mathcal{C}_r(H)$ be the family consisting of every edge-colored copy of $H$ which uses exactly $r$ colors. In this paper we consider a variety of colored saturation problems. We determine the order of magnitude for $mathrm{sat}_t(n, mathcal{C}_r(K_k))$ for all $r$, showing a sharp change in behavior when $rgeq binom{k-1}{2}+2$. A particular case of this theorem proves a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We determine $mathrm{sat}_t(n, mathcal{C}_2(K_3))$ exactly and determine the extremal graphs. Additionally, we document some interesting irregularities in the colored saturation function.



قيم البحث

اقرأ أيضاً

113 - Barnaby Roberts 2015
We look at several saturation problems in complete balanced blow-ups of graphs. We let $H[n]$ denote the blow-up of $H$ onto parts of size $n$ and refer to a copy of $H$ in $H[n]$ as partite if it has one vertex in each part of $H[n]$. We then ask ho w few edges a subgraph $G$ of $H[n]$ can have such that $G$ has no partite copy of $H$ but such that the addition of any new edge from $H[n]$ creates a partite $H$. When $H$ is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger. Our main result is to calculate this value for $H=K_4$ when $n$ is large. We also give exact results for paths and stars and show that for $2$-connected graphs the answer is linear in $n$ whilst for graphs which are not $2$-connected the answer is quadratic in $n$. We also investigate a similar problem where $G$ is permitted to contain partite copies of $H$ but we require that the addition of any new edge from $H[n]$ creates an extra partite copy of $H$. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.
It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Delta^{mon}(G)leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker result s for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta-H{a}ggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge- colored graph. We first prove that for all integers $s$ and $t$ with $tgeq sgeq2$, every edge-colored graph $G$ with no properly colored $K_{s,t}$ contains a spanning subgraph $H$ which admits an orientation $D$ such that every directed cycle in $D$ is a properly colored cycle in $G$. Using this result, we show that for $rgeq4$, if the Caccetta-H{a}ggkvist Conjecture holds , then every edge-colored graph of order $n$ with minimum color degree at least $n/r+2sqrt{n}+1$ contains a properly colored cycle of length at most $r$. In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) $K_{s,t}$.
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rain bow $ell$-cycle $C_{ell}$ whenever $n ge 432 ell$. This result is sharp for all odd integers $ell geq 3$, and extends earlier work of the authors for when $ell$ is even.
Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delta^c(G)$ denote the minimum color degree of $G$. A subgraph $F$ of $G$ is called rainbow if all edges of $F$ have pairwise distinct colors. There have been a lot results on rainbo w cycles of edge-colored graphs. In this paper, we show that (i) if $delta^c(G)>frac{3n-3}{4}$, then every vertex of $G$ is contained in a rainbow triangle; (ii) $delta^c(G)>frac{3n}{4}$, then every vertex of $G$ is contained in a rainbow $C_4$; and (iii) if $G$ is complete, $ngeq 8k-18$ and $delta^c(G)>frac{n-1}{2}+k$, then $G$ contains a rainbow cycle of length at least $k$. Some gaps in previous publications are also found and corrected.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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