Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets

Details Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets

2005-11-10

arxiv.org/abs/math/0511262v2

Combinatorica 29.4:449-466, 2009

Mathematics

Combinatorics

Scientific paper

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 $\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,...,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$. Suppose that $\chi(G_i,F)\leq k$ and $S$ is a $k$-multiplicative Sidon set of cardinality $d$. We prove that $\chi(H,F) \leq 1+2k\cdot\max S$. We then prove that the maximum density of a $k$-multiplicative Sidon set is $\Theta(1/\log k)$. It follows that $\chi(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.

Affiliated with

Also associated with

No associations

Rating

Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-386517