Research output per year
Research output per year
Attila Pór, David R. Wood
Research output: Contribution to journal › Article › Research › peer-review
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 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 a x = b y implies a = b and x = y whenever x, y ∈ S and 1 ≤ a, b ≤ k. Suppose that χ (G _{i}, F) ≤ k and S is a k-multiplicative Sidon set of cardinality d. We prove that χ (H, F) ≤ 1 + 2 k ṡ m a x S. We then prove that the maximum density of a k-multiplicative Sidon set is Θ (1 / log k). It follows that χ (H, F) ≤ O (d k log k).
Original language | English |
---|---|
Pages (from-to) | 33-40 |
Number of pages | 8 |
Journal | Electronic Notes in Discrete Mathematics |
Volume | 28 |
DOIs | |
Publication status | Published - 1 Mar 2007 |
Externally published | Yes |
Research output: Contribution to journal › Article › Research › peer-review