Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets 1

Let F be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph G with no bichromatic subgraph in F is F-free. The F-free chromatic number χ(G,F) of a graph G is the minimum number of colours in an F-free colouring of G. For appropriate choices of F, several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies F-free colourings of the cartesian product of graphs. Let H be the cartesian product of the graphs G1,G2,…,Gd. Our main result establishes an upper bound on the F-free chromatic number of H in terms of the maximum F-free chromatic number of the Gi and the following number-theoretic concept. A set S of natural numbers is k-multiplicative Sidon if ax=by implies a=b and x=y whenever x,y∈S and 1⩽a,b⩽k. Suppose that χ(Gi,F)⩽k and S is a k-multiplicative Sidon set of cardinality d. We prove that χ(H,F)⩽1+2k⋅maxS. We then prove that the maximum density of a k-multiplicative Sidon set is Θ(1/logk). It follows that χ(H,F)⩽O(dklogk).