Anti-Ramsey Problems in Complete Bipartite Graphs for t Edge-Disjoint Rainbow Spanning Subgraphs: Cycles and Matchings

2019 
A subgraph H of an edge-colored graph G is rainbow if all of its edges have different colors. The anti-Ramsey number is the maximum number of colors in an edge-coloring of G with no rainbow copy of H. Originally a complete graph was considered as G. In this paper, we consider a complete bipartite graph as the host graph and discuss some results for the graph H being hamiltonian cycle and perfect matching. Let \(c(K_{p,p},t)\) and \(m(K_{p,p},t)\) be the maximum number of colors in an edge-coloring of the complete bipartite graph \(K_{p,p}\) not having t edge-disjoint rainbow hamiltonian cycles and perfect matchings, respectively. We prove that \(c(K_{p,p},t)=p^2-p+t\) for \(t \ge 2\), \(p\ge 4t-1\) and \(m(K_{p,p},t)=p^2-2p+t+1\) for \(t \ge \)2, \(p\ge 2t+8\).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    19
    References
    6
    Citations
    NaN
    KQI
    []