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\).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
19
References
6
Citations
NaN
KQI