×

Graph coloring and Graham’s greatest common divisor problem. (English) Zbl 1378.05046

Summary: In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer \(k\) consider a graph \(B_k\) whose vertex set is the set of all positive integers with two vertices \(a, b\) joined by an edge whenever the two numbers \(a/\gcd(a, b)\) and \(b/\gcd(a, b)\) are both at most \(k\). We conjecture that the chromatic number of every such graph \(B_k\) is equal to \(k\). This would generalize the greatest common divisor problem of R. L. Graham [“Unsolved problem 5749”, Amer. Math. Monthly, 77, 775 (1970)]; in graph-theoretic terminology it states that the clique number of \(B_k\) is equal to \(k\). Our conjecture is connected to integer lattice tilings and partial Latin squares completions.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, R. C.; Harman, G.; Pintz, J., The difference between consecutive primes, II, Proc. Lond. Math. Soc. (3), 83, 532-562 (2001) · Zbl 1016.11037
[2] Balasubramanian, R.; Soundararajan, K., On a conjecture of R.L. Graham, Acta Arith., LXXV.1, 1-38 (1996) · Zbl 0853.11002
[3] Bartnicki, T.; Bosek, B.; Czerwiński, S.; Grytczuk, J.; Matecki, G.; Żelazny, W., Additive colorings of planar graphs, Graphs Combin., 30, 1087-1098 (2013) · Zbl 1298.05102
[4] Czerwiński, S.; Grytczuk, J.; Żelazny, W., Lucky labelings of graphs, Inform. Process. Lett., 109, 1078-1081 (2009) · Zbl 1197.05125
[5] Forcade, R.; Lomeraux, J.; Pollington, A., A group of two problems in groups, Amer. Math. Monthly, 93, 119-121 (1986)
[6] Forcade, R.; Pollington, A., What is special about 195? Groups, \(n\) th power maps and a problem of Graham, (Mollin, Richard A., Number Theory (1990)), 147-155 · Zbl 0697.10009
[7] Graham, R. L., Unsolved problem 5749, Amer. Math. Monthly, 77, 775 (1970)
[8] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: towards 1-2-3-conjecture, J. Combin. Theory B, 100, 347-349 (2010) · Zbl 1209.05087
[9] Karoński, M.; Łuczak, T.; Thomason, A., Edge veights and vertex colours, J. Combin. Theory B, 91, 151-157 (2004) · Zbl 1042.05045
[10] Marica, J.; Schönheim, J., Differences of sets and a problem of Graham, Canad. Math. Bull., 12, 635-637 (1969) · Zbl 0192.33202
[11] Szegedy, M., The solution of Graham’s greatest common divisor problem, Combinatorica, 6, 67-71 (1986) · Zbl 0593.10002
[12] 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.