Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets

preprint2008arXivOpen access

Abstract

Let FF be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph GG with no bichromatic subgraph in FF is $\F$-free. The FF-free chromatic number χ(G,F)χ(G,F) of a graph GG is the minimum number of colours in an FF-free colouring of GG. For appropriate choices of FF, several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies FF-free colourings of the cartesian product of graphs. Let HH be the cartesian product of the graphs G1,G2,...,GdG_1,G_2,...,G_d. Our main result establishes an upper bound on the FF-free chromatic number of HH in terms of the maximum FF-free chromatic number of the GiG_i and the following number-theoretic concept. A set SS of natural numbers is kk-multiplicative Sidon if ax=byax=by implies a=ba=b and x=yx=y whenever x,y∈Sx,y\in S and 1≤a,b≤k1\leq a,b\leq k. Suppose that χ(Gi,F)≤kχ(G_i,F)\leq k and SS is a kk-multiplicative Sidon set of cardinality dd. We prove that χ(H,F)≤1+2k⋅max⁡Sχ(H,F) \leq 1+2k\cdot\max S. We then prove that the maximum density of a kk-multiplicative Sidon set is Θ(1/log⁡k)Θ(1/\log k). It follows that χ(H,F)≤O(dklog⁡k)χ(H,F) \leq O(dk\log k). We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.