English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Pro

Presents the zaia usage as premium feature

ZAIA

Presents AI Discovery search usage as a premium feature

AI Discovery

Presents AI Discovery explain and summary usage as a premium feature

Content Analysis

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Presents the pdf analysis as premium feature

PDF Analysis

1500 Top-up

3000 Top-up

Zendy Basic

2500 Top-up

Zendy Unlimited

Presents the access of premium content as premium feature

Premium Content

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 gJ(1/log k). It follows that χ(H,F)≤$$\mathcal{O}$$(dk logk). We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.

Colourings of the cartesian product of graphs and multiplicative Sidon sets