COLOURINGS OF THE CARTESIAN PRODUCT OF GRAPHS AND MULTIPLICATIVE SIDON SETS

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 chi(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 G(1),G(2),...,G(d). 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 G(i) 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 is an element of S and 1 <= a, b <= k. Suppose that chi(G(i),F) <= k and S is a k-multiplicative Sidon set of cardinality d. We prove that chi(H,F) <= 1 + 2k . max S. We then prove that the maximum density of a k-multiplicative Sidon set is Theta (1/log k). It follows that chi(H, F) <= O(dk log k). We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.