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 Graham from 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.