اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRainbow spanning structures in graph and hypergraph systems
146
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study the following rainbow version of subgraph containment problems in a family of (hyper)graphs, which generalizes the classical subgraph containment problems in a single host graph. For a collection $textbf{G}={G_1, G_2,ldots, G_{m}}$ of not necessarily distinct graphs on the same vertex set $[n]$, a (sub)graph $H$ on $[n]$ is rainbow if $E(H)subseteq bigcup_{iin [m]}E(G_i)$ and $|E(H)cap E(G_i)|le 1$ for $iin[m]$. Note that if $|E(H)|=m$, then a rainbow $H$ consists of exactly one edge from each $G_i$. Our main results are on rainbow clique-factors in (hyper)graph systems with minimum $d$-degree conditions. In particular, (1) we obtain a rainbow analogue of an asymptotical version of the Hajnal--Szemer{e}di theorem, namely, if $tmid n$ and $delta(G_i)geq(1-frac{1}{t}+varepsilon)n$ for each $iin[frac{n}{t}binom{t}{2}]$, then $textbf{G}$ contains a rainbow $K_t$-factor; (2) we prove that for $1le dle k-1$, essentially a minimum $d$-degree condition forcing a perfect matching in a $k$-graph also forces rainbow perfect matchings in $k$-graph systems. The degree assumptions in both results are asymptotically best possible (although the minimum $d$-degree condition forcing a perfect matching in a $k$-graph is in general unknown). For (1) we also discuss two direct
قيم البحث
اقرأ أيضاً
A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph $K_{2n}$, there exists a decomposition of $K_{2n}$ into is
omorphic rainbow spanning trees. This settles conjectures of Brualdi--Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.
A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for $n$ and $C$ large enough, if $G$ is an edge-colored copy of $K_n$ in which each color class has si
ze at most $n/2$, then $G$ has at least $lfloor n/(Clog n)rfloor$ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if $G$ is any edge-colored graph with $n$ vertices in which each color appears on at most $deltacdotlambda_1/2$ edges, where $deltageq Clog n$ for $n$ and $C$ sufficiently large and $lambda_1$ is the second-smallest eigenvalue of the normalized Laplacian matrix of $G$, then $G$ contains at least $leftlfloorfrac{deltacdotlambda_1}{Clog n}rightrfloor$ edge-disjoint rainbow spanning trees.
A spanning tree of an edge-colored graph is rainbow provided that each of its edges receives a distinct color. In this paper we consider the natural extremal problem of maximizing and minimizing the number of rainbow spanning trees in a graph $G$. Su
ch a question clearly needs restrictions on the colorings to be meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles, known in the literature as JL-colorings, there turns out to be a particularly nice way of counting the rainbow spanning trees and we solve this problem completely for JL-colored complete graphs $K_n$ and complete bipartite graphs $K_{n,m}$. In both cases, we find tight upper and lower bounds; the lower bound for $K_n$, in particular, proves to have an unexpectedly chaotic and interesting behavior. We further investigate this question for JL-colorings of general graphs and prove several results including characterizing graphs which have JL-colorings achieving the lowest possible number of rainbow spanning trees. We establish other results for general $n-1$ colorings, including providing an analogue of Kirchoffs matrix tree theorem which yields a way of counting rainbow spanning trees in a general graph $G$.
An edge-colored graph $G$ is called textit{rainbow} if every edge of $G$ receives a different color. Given any host graph $G$, the textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the m
aximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this paper, we determine $r(G,t)$ for all host graphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P_0$ with $|E(G)|-|E(P_0,G)|<t(|P_0|-1)$; and $r(G,t)=max_{Pcolon |P|geq 3} {|E(P,G)|+t(|P|-2)}$ otherwise. As a corollary, we determine $r(K_{p,q},t)$ for all values of $p,q, t$, improving a result of Jia, Lu and Zhang.
We survey recent advances in the theory of graph and hypergraph decompositions, with a focus on extremal results involving minimum degree conditions. We also collect a number of intriguing open problems, and formulate new ones.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
