×

From the 1-2-3 conjecture to the Riemann hypothesis. (English) Zbl 1458.05069

Summary: This survey presents some combinatorial problems with number-theoretic flavor. Our journey starts from a simple graph coloring question, but at some point gets close to dangerous territory of the Riemann Hypothesis. We will mostly focus on open problems, but we will also provide some simple proofs, just for adorning.

MSC:

05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Addario-Berry, L.; Dalal, K.; Reed, B., Degree constrained subgraphs, Discrete Appl. Math., 156, 1168-1174 (2008) · Zbl 1147.05055
[2] Alon, N., Combinatorial Nullstellensatz, Combin. Probab. Comput., 8, 7-29 (1999) · Zbl 0920.05026
[3] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049
[4] Apostol, T. M., Introduction to Analytic Number Theory (1998), Springer-Verlag: Springer-Verlag New York · Zbl 1154.11300
[5] Balasubramanian, R.; Soundararajan, K., On a conjecture of R.L. Graham, Acta Arith., LXXV.1, 1-38 (1996) · Zbl 0853.11002
[6] Bartnicki, T.; Bosek, B.; Czerwiński, S.; Grytczuk, J.; Matecki, G.; Żelazny, W., Additive coloring of planar graphs, Graphs Combin., 30, 1087-1098 (2014) · Zbl 1298.05102
[7] Bartnicki, T.; Grytczuk, J.; Niwczyk, S., Weight choosability of graphs, J. Graph Theory, 60, 242-256 (2009) · Zbl 1210.05138
[8] Bennett, P.; Dudek, A.; Frieze, A.; Helenius, L., Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs, Electron. J. Combin., 23, 21 (2016), Paper 2.46 · Zbl 1339.05269
[9] Borwein, P.; Choi, S. K.K.; Coons, M., Completely multiplicative functions taking values in \(\{ - 1 , 1 \}\), Trans. Amer. Math. Soc., 362, 6279-6291 (2010) · Zbl 1222.11111
[10] Borwein, P.; Choi, S.; Rooney, B.; Weirathmueller, A., The Riemann Hypothesis (2007), Springer-Verlag: Springer-Verlag New York · Zbl 1132.11047
[11] Bosek, B.; Dębski, M.; Grytczuk, J.; Sokół, J.; Śleszyńska-Nowak, M.; Żelazny, W., Graph coloring and Graham’s greatest common divisor problem, Discrete Math., 341, 781-785 (2018) · Zbl 1378.05046
[12] B. Bosek, J. Grytczuk, K. Kaszuba, W. Łopata, M. Zając, Playing with signs and primes, (manuscript).
[13] A.E. Caicedo, T.A.C. Chartier, P.P. Pach, Coloring the \(n\)-smooth numbers with \(n\) colors, Arxiv. · Zbl 1468.11077
[14] Czerwiński, S.; Grytczuk, J.; Żelazny, W., Lucky labelings of graphs, Inform. Process. Lett., 109, 1078-1081 (2009) · Zbl 1197.05125
[15] Dudek, A.; Wajc, D., On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci., 13, 45-50 (2011) · Zbl 1283.05093
[16] Erdős, P., Some unsolved problems, Michigan Math. J., 4, 299-300 (1957)
[17] Graham, R. L., Unsolved problem 5749, Amer. Math. Monthly, 77, 775 (1970)
[18] Grytczuk, J., Thue type problems for graphs, points, and numbers, Discrete Math., 308, 4419-4429 (2008) · Zbl 1160.05036
[19] Kalkowski, M., A Note on the 1, 2-Conjecture (2009), (Ph.D. Thesis)
[20] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: towards 1-2-3-conjecture, J. Combin. Theory Ser. B, 100, 347-349 (2010) · Zbl 1209.05087
[21] Kalkowski, M.; Karonski, M.; Pfender, F., The 1-2-3-conjecture for hypergraphs, J. Graph Theory, 85, 706-715 (2017) · Zbl 1367.05151
[22] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157 (2004) · Zbl 1042.05045
[23] Kreutzer, S.; Oum, S.; Seymour, P.; van der Zypen, D.; Wood, D. R., Majority Colouring of Digraphs, Electron. J. Combin., 24, P2.25 (2017) · Zbl 1364.05029
[24] Pólya, G., Verschiedene Bemerkungen zur Zahlentheorie, Jahresber. Dtsch. Math.-Ver., 28, 31-40 (1919) · JFM 47.0882.06
[25] J. Przybyło, The 1-2-3 Conjecture almost holds for regular graphs, arXiv:1809.10761.
[26] Przybyło, J.; Woźniak, M., On a 1-2 conjecture, Discrete Math. Theoret. Comput. Sci., 12, 101-108 (2010) · Zbl 1250.05093
[27] Przybyło, J.; Woźniak, M., Total weight choosability of graphs, Electron. J. Combin., 18, P112 (2011) · Zbl 1217.05202
[28] Soundararajan, K., Tao’s resolution of the Erdős discrepancy problem, Bull. Amer. Math. Soc., 55, 81-92 (2018) · Zbl 1440.11144
[29] Szegedy, M., The solution of Graham’s greatest common divisor problem, Combinatorica, 6, 67-71 (1986) · Zbl 0593.10002
[30] Tao, T., The Erdős discrepancy problem, Discrete Anal. (2016), Paper No. 1, 29 · Zbl 1353.11087
[31] Vučković, B., Multi-set neighbor distinguishing 3-edge coloring, Discrete Math., 341, 820-824 (2018) · Zbl 1378.05074
[32] Wong, T.; Zhu, X., Total weight choosability of graphs, J. Graph Theory, 66, 198-212 (2011) · Zbl 1228.05161
[33] Wong, T.; Zhu, X., Every graph is \(( 2 , 3 )\)-choosable, Combinatorica, 36, 121-127 (2016) · Zbl 1374.05106
[34] Zaharescu, A., On a conjecture of Graham, J. Number Theory, 27, 33-40 (1987) · Zbl 0629.10003
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.