Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'488'730
Articles rated: 2609

29 March 2024
 
  » arxiv » math/0511262

 Article overview


Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets
Attila Pór ; David R. Wood ; PostScript ; PDF ; Other formats ;
Date 10 Nov 2005
Subject Combinatorics; Number Theory
AbstractLet $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,yin S$ and $1leq a,bleq 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+2kcdotmax 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(dklog k)$. We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.
Source arXiv, math/0511262
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser claudebot






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica