×

Anti-van der Waerden numbers on graphs. (English) Zbl 1493.05205

Summary: 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.

MSC:

05C55 Generalized Ramsey theory
05D10 Ramsey theory
05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
05C05 Trees
11B25 Arithmetic progressions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Axenovich, M.; Fon-Der-Flaass, D., On rainbow arithmetic progressions, Electron. J. Combin., 11, 1, 7 (2004) · Zbl 1060.11005 · doi:10.37236/1754
[2] Axenovich, M.; Martin, RR, Sub-Ramsey numbers for arithmetic progressions, Graphs Comb., 22, 1, 297-309 (2006) · Zbl 1106.05097 · doi:10.1007/s00373-006-0663-2
[3] Berikkyzy, Z.; Schulte, A.; Young, M., Anti-van der Waerden numbers of 3-term arithmetic progressions, Electron. J. Comb., 24, 2, 9 (2017) · Zbl 1366.11019
[4] Butler, S.; Erickson, C.; Hogben, L.; Hogenson, K.; Kramer, L.; Kramer, RL; Lin, J.; Martin, RR; Stolee, D.; Warnberg, N.; Young, M., Rainbow arithmetic progressions, J. Comb., 7, 4, 595-626 (2016) · Zbl 1350.05171
[5] Erdős, P.; Simonovits, M.; Sós, V., Anti-Ramsey theorems, Infinite Finite Sets, II, 633-643 (1975) · Zbl 0316.05111
[6] Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory: a dynamic survey. Theory Appl. Graphs 0(1), Article 1 (2014) · Zbl 1231.05178
[7] Gerencesíer, L.; Gyárfás, A., On Ramsey-type problems, Annales Universitatis Scientiarum Budapestinesis, Eötvös Sect. Math., 10, 167-170 (1967) · Zbl 0163.45502
[8] 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) · Zbl 1128.11305
[9] Radziszowski, S., Small Ramsey numbers, Electron. J. Comb., 1, 15, 104 (2021)
[10] Rehm, H.; Schulte, A.; Warnberg, N., Anti-van der Waerden numbers of graph products, Australas. J. Comb., 73, 3, 486-500 (2018) · Zbl 1411.05229
[11] Uherka, K.: An introduction to Ramsey theory and anti-Ramsey theory on the integers. Master’s Creative Component, Iowa State University (2013)
[12] van der Waerden, B., Beweis einer baudetschen vermutung, Nieuw Arch. Wisk., 19, 212-216 (1927) · JFM 53.0073.12
[13] Young, M., Rainbow arithmetic progressions in finite Abelian groups, J. Comb., 9, 4, 619-629 (2018) · Zbl 1401.05297
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.