Anti-van der Waerden Numbers on Graphs
Tóm tắt
In this paper arithmetic progressions on the integers and the integers modulo n are extended to graphs. A k-term arithmetic progression of a graph G (k-AP) is a list of k distinct vertices such that the distance between consecutive pairs is constant. A rainbow k-AP is a k-AP where each vertex is colored distinctly. This allows for the definition of the anti-van der Waerden number of a graph G, which is the least positive integer r such that every exact r-coloring of G contains a rainbow k-AP. Much of the focus of this paper is on 3-term arithmetic progressions for which general bounds are obtained based on the radius and diameter of a graph. The general bounds are improved for trees and Cartesian products and exact values are determined for some classes of graphs. Longer k-term arithmetic progressions are considered and a connection between the Ramsey number of paths and the anti-van der Waerden number of graphs is established.Please confirm if the inserted city and country name for all affiliations is correct. Amend if necessary.The cities and affiliations are correct.
Tài liệu tham khảo
Axenovich, M., Fon-Der-Flaass, D.: On rainbow arithmetic progressions. Electron. J. Combin. 11(1), 7 (2004). (Research Paper 1)
Axenovich, M., Martin, R.R.: Sub-Ramsey numbers for arithmetic progressions. Graphs Comb. 22(1), 297–309 (2006)
Berikkyzy, Z., Schulte, A., Young, M.: Anti-van der Waerden numbers of 3-term arithmetic progressions. Electron. J. Comb. 24(2), 9 (2017). (Paper 2.39)
Butler, S., Erickson, C., Hogben, L., Hogenson, K., Kramer, L., Kramer, R.L., Lin, J., Martin, R.R., Stolee, D., Warnberg, N., Young, M.: Rainbow arithmetic progressions. J. Comb. 7(4), 595–626 (2016)
Erdős, P., Simonovits, M., Sós, V.: Anti-Ramsey theorems. Infinite Finite Sets II, 633–643 (1975). ((Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday))
Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory: a dynamic survey. Theory Appl. Graphs 0(1), Article 1 (2014)
Gerencesíer, L., Gyárfás, A.: On Ramsey-type problems. Annales Universitatis Scientiarum Budapestinesis, Eötvös Sect. Math. 10, 167–170 (1967)
Jungić, V., Licht, J., Mahdian, M., Nes̆etril, J., Radoic̆ić, R.: Rainbow arithmetic progressions and anti-Ramsey results. Comb. Probab. Comput. 12(5–6), 599–620 (2003)
Radziszowski, S.: Small Ramsey numbers. Electron. J. Comb. 1(15), 104 (2021)
Rehm, H., Schulte, A., Warnberg, N.: Anti-van der Waerden numbers of graph products. Australas. J. Comb. 73(3), 486–500 (2018)
Uherka, K.: An introduction to Ramsey theory and anti-Ramsey theory on the integers. Master’s Creative Component, Iowa State University (2013)
van der Waerden, B.: Beweis einer baudetschen vermutung. Nieuw Arch. Wisk. 19, 212–216 (1927)
Young, M.: Rainbow arithmetic progressions in finite Abelian groups. J. Comb. 9(4), 619–629 (2018)