Graph coloring and Graham's greatest common divisor problem

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 Bk 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 Bk is equal to k. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of Bk is equal to k. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.