Anti-Ramsey Problems in Complete Bipartite Graphs for t Edge-Disjoint Rainbow Spanning Trees
2020
Let
$$r(K_{p,q},t)$$
be the maximum number of colors in an edge-coloring of the complete bipartite graph
$$K_{p,q}$$
not having t edge-disjoint rainbow spanning trees. We prove that
$$r(K_{p,p},1)=p^2-2p+2$$
for
$$p\ge 4$$
and
$$r(K_{p,q},1)=pq-2q+1$$
for
$$p>q\ge 4$$
. Let
$$t\ge 2$$
. We also show that
$$r(K_{p,p},t)=p^2-2p+t+1$$
for
$$p \ge 2t+\sqrt{3t-3}+4$$
and
$$r(K_{p,q},t)=pq-2q+t$$
for
$$p > q \ge 2t+\sqrt{3t-2}+4$$
.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
4
Citations
NaN
KQI