报告题目： Planar anti-Ramsey numbers and Turan numbers for paths and cycles
报告人：Yongtang Shi (南开大学)
时间地点： 5月25日下午4：00-5:00 后主楼1124
报告摘要：Motivated by anti-Ramsey numbers introduced by Erdos, Simonovits and Sos in 1975, we study the anti-Ramsey problem when host graphs are plane triangulations. Given a positive integer n and a plane graph H, let Tn(H) be the family of all plane triangulations T on n vertices such that T contains H as a subgraph. The planar anti-Ramsey number of H, denoted arP(n,H), is the maximum number k such that no edge-coloring of any plane triangulation in Tn(H) with k colors contains a rainbow copy of H. The study of arP(n,H) (under the name of rainbow numbers) was initiated by Hornak, Jendrol, Schiermeyer and Sotak [J Graph Theory 78 (2015) 248–257]. We study planar anti-Ramsey numbers for paths and cycles. We first establish lower bounds for arP(n,Pk) when n ≥ k ≥ 8. We then improve the existing lower bound for arP(n,Ck) when k ≥ 5 and n ≥ k2 - k. Finally, using the main ideas in the above- mentioned paper, we obtain upper bounds for arP (n, C6) when n ≥ 8 and arP (n, C7) when n ≥ 13, respectively.
Turan-type problems was initiated by Mantel (1907) and Turan (1941), which wasgeneralized soon by Erdos et al. Dirac (1964) and Mader (1967) started to investigate extremal problems for Kt-minor-free graphs. The planar Turan number of F, denoted exP(n,F), is the maximum number of edges of any F-free planar graph on n vertices. Dowden [J. Graph Theory 83(2016) 213–230] began the study of planar Turan num- bers exP(n,H) (under the name of “extremal” planar graphs) and determined that exP(n,C4)≤15/7(n-2) for all n≥4 and exP(n,C5)≤(12n-33)/5 for all n≥11,and also proved that both of those bounds are tight. Dowden suggested studying the case of larger cycles and other forbidden subgraphs, such as K4 minus one edge. In this paper, we show that exP(n,C6)≤18/7(n-2) for all n≥6. We also determine exP(n,Θk) for k = 4, 5, where Θk is the graph obtained from Ck by adding one chord. Finally, we determine the value of exP (n, Pk ) for k ≤ 11 and characterize all the extremal graphs.
Joint work with Yongxin Lan and Zi-Xia Song.