| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
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 | Abstract: | 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,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 |
|
|
No review found.
Did you like this article?
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
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |