Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets

Attila Pór, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)


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 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 a x = b y implies a = b and x = y whenever x, y ∈ S and 1 ≤ a, b ≤ k. Suppose that χ (G i, F) ≤ k and S is a k-multiplicative Sidon set of cardinality d. We prove that χ (H, F) ≤ 1 + 2 k ṡ m a x S. We then prove that the maximum density of a k-multiplicative Sidon set is Θ (1 / log k). It follows that χ (H, F) ≤ O (d k log k).

Original languageEnglish
Pages (from-to)33-40
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Publication statusPublished - 1 Mar 2007
Externally publishedYes

Cite this