Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecompositions into isomorphic rainbow spanning trees
77
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 isomorphic rainbow spanning trees. This settles conjectures of Brualdi--Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.
rate research
Read More
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 size 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$. Such 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 maximum 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.
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 asymptotically-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)$.
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
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
