Fans and bundles in the graph of pairwise sums and products

Lorenz Halbeisen

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

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$.

Détail

DOI : 10.37236/1759

Classification : 11B75, 05D10, 11D99, 05C15
Mots-clés : graph on integers, chromatic number