If $G$ is an infinite graph where $v_{i,j}$ is joined with $v_{k,i+j}$ for all $k,i,j$ then is the chromatic number of G always infinite? Suppose $G$ is an infinite graph with vertices labelled as $v_{i,j}$ such that $i,j$ are positive integers (so we assume that there are denumerable many vertices of the graph). For any two positive integers $i,j$ we join the vertex $v_{i,j}$ with all the vertices $v_{k,i+j}$ for every $k \in \mathbb{N}.$
Is the chromatic number of the graph $G$ necessarily infinite?
 A: For every $n \in \mathbb{N}$, $G$ contains a copy of the $n$th shift graph, $G_n$.  These are a classic construction of (finite) triangle-free graphs with arbitrarily large chromatic number.  The vertices of $G_n$ are all intervals $[i,j]$ with $1 \leq i < j \leq n$.  Two intervals $[i,j]$ and $[k,\ell]$ are adjacent if $j=k$ or $\ell=i$.  It is well-known that $G_n$ has chromatic number  $\lceil \log_2 n \rceil$.
Now, let $f:V(G_n) \to V(G)$ be defined by $f([i,j])=v_{j-i,i}$.  Clearly, $f$ is an injective homomorphism, and so $G_n$ is a subgraph of $G$ for all $n$.  Thus, $G$ has infinite chromatic number. This answers a question of Fedor Petrov asked in a comment to Ilya Bogdanov's answer.  Actually, the proof that the shift graphs have unbounded chromatic number is the same argument given in Ilya's answer.
A: The chromatic number is indeed infinite.
Assume that there is a proper coloring in finitely many colors. Denote by $S_i$ the set of colors of the vertices having the form $v_{k,i}$ (for some $k$). There are two equal sets, say $S_i$ and $S_j$ with $i<j$. Then the color  of $v_{j-i,i}$ lies in that set, and therefore is also a color of some vertex $v_{k,j}$; but those vertices are adjacent.
