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$$ .
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    16
    References
    4
    Citations
    NaN
    KQI
    []