Fans and Bundles in the Graph of Pairwise Sums and Products

Lorenz Halbeisen

Abstract


Let $G^{\times}_{+}$ be the graph on the vertex-set the positive integers ${\Bbb{N}}$, with $n$ joined to $m$ if $n\neq m$ and for some $x,y\in{\Bbb{N}}$ we have $x+y=n$ and $x\cdot y=m$. A pair of triangles sharing an edge (i.e., a $K_4$ with an edge deleted) and containing three consecutive numbers is called a $2$-fan, and three triangles on five numbers having one number in common and containing four consecutive numbers is called a $3$-fan. It will be shown that $G^{\times}_{+}$ contains $3$-fans, infinitely many $2$-fans and even arbitrarily large "bundles" of triangles sharing an edge. Finally, it will be shown that $\chi\big(G^{\times}_{+}\big)\ge 4$.


Full Text: PDF