Abstract
Let be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph with no bichromatic subgraph in is $\F$-free. The -free chromatic number of a graph is the minimum number of colours in an -free colouring of . For appropriate choices of , several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies -free colourings of the cartesian product of graphs. Let be the cartesian product of the graphs . Our main result establishes an upper bound on the -free chromatic number of in terms of the maximum -free chromatic number of the and the following number-theoretic concept. A set of natural numbers is -multiplicative Sidon if implies and whenever and . Suppose that and is a -multiplicative Sidon set of cardinality . We prove that . We then prove that the maximum density of a -multiplicative Sidon set is . It follows that . We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.