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 $\text{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,\mathrm{.}\mathrm{.}\mathrm{.},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\in S$ and $1\leq a,b\leq k$\mathrm{.}Supposethat$\chi(G_i,F)\leq k$and$S$isa$k$-multiplicative Sidon set of cardinality $d$. We prove that $\chi (H,F)\le 1+2k\cdot \max S$. We then prove that the maximum density of a $k$-multiplicative Sidon set is $\mathrm{\Theta }(1\mathrm{/}\log k)$. It follows that $\chi (H,F)\le O(dk\log k)$. We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.