Anti-Ramsey Problems in Complete Bipartite Graphs for t Edge-Disjoint Rainbow Spanning Trees
- PDF / 400,181 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 188 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Anti-Ramsey Problems in Complete Bipartite Graphs for t Edge-Disjoint Rainbow Spanning Trees Yuxing Jia1 • Mei Lu1 • Yi Zhang2 Received: 2 March 2020 / Accepted: 22 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Let rðKp;q ; tÞ be the maximum number of colors in an edge-coloring of the complete bipartite graph Kp;q not having t edge-disjoint rainbow spanning trees. We prove that rðKp;p ; 1Þ ¼ p2 2p þ 2 for p 4 and rðKp;q ; 1Þ ¼ pq 2q þ 1 for p [ q 4. pffiffiffiffiffiffiffiffiffiffiffiffiffi Let t 2. We also show that rðKp;p ; tÞ ¼ p2 2p þ t þ 1 for p 2t þ 3t 3 þ 4 pffiffiffiffiffiffiffiffiffiffiffiffiffi and rðKp;q ; tÞ ¼ pq 2q þ t for p [ q 2t þ 3t 2 þ 4. Keywords Complete bipartite graph Rainbow Anti-Ramsey problem Spanning tree
Mathematics Subject Classification 05C55 05C35 05C38 05C04
1 Introduction An edge colored graph is called rainbow if all the colors on the edges are distinct. A rainbow copy of a graph H in an edge-colored graph G is a subgraph of G isomorphic to H such that the coloring restricted to the subgraph is a rainbow coloring. The anti-Ramsey problem is to decide the maximum number of colors in the edge coloring of G which does not contain a rainbow copy of H. We denote such maximum number of colors by AR(G, H). Anti-Ramsey number was introduced by & Yi Zhang [email protected] Yuxing Jia [email protected] Mei Lu [email protected] 1
Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
2
School of Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China
123
Graphs and Combinatorics
Erd}os, Simonovits and So´s in the 1970s [5] and considered in the classical case when G ¼ Kn . In the same paper, they showed that the anti-Ramsey number ARðKn ; HÞ is closely related to Tura´n number. The anti-Ramsey numbers for some special graph classes in complete graph have been determined (see [1, 4, 5, 11, 12, 16, 17]). The paper of Fujita, Magnant and Ozeki [6] presents a survey of results in classical and nonclassical case. Among these results, Bialostocki and Voxman [3] determined the maximum number of colors in an edge-coloring of Kn with no rainbow spanning tree. Haas and Young [7] determined the maximum number with no rainbow spanning matching (for even n). Jahanbekam and West [8] extended these two results and determined the maximum number of colors in an edge-coloring of Kn not having t edge-disjoint rainbow spanning matchings (when t 2, n [ 4t þ 10), spanning cycles (when t 2, n 8t 1) and spanning trees pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi (when t 1, n [ 2t þ 6t 23=4 þ 5=2 and n ¼ 2t). There are also some results when the host graph is bipartite (see for example [2, 13]-[15]). In particular, Li and Xu [14] proved that ARðKm;n ; kK2 Þ ¼ mðk 2Þ þ 1 for all m n k 3, where kK2 is a matching of size k. Axenovich and Jiang [2] obtained ARðKm;n ; C2k Þ for all positive integers m, n, k with m n and k 2. In [10], we show that cðKp;p ; tÞ ¼ p2 p þ t for t 2, p 4
Data Loading...
