Borel coloring of a graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$ The following question was asked in a comment by Joel David Hamkins in Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$.
Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let $$E:=\big\{\{f,g\}: f, g \in V \land f\neq g\land \exists k\in \mathbb{N} \text{ }\forall n\in\mathbb{N}\setminus\{k\} (f(n) = g(n))\big\}.$$
Let $G=(V,E)$. This graph is Borel. Can there be a Borel $\mathbb{N}$-coloring?
 A: No. Otherwise there is a Borel non meager set $B$ such that for every $k$, $B + e_k$ is disjoint with $B$. $B$ is comeager in some basic clopen set $C$. Choose $k$ larger than the support of $C$, then $B, B + e_k$ are both comeager in $C$. Contradiction.
A: It's worth pointing out that in the context of Borel chromatic numbers, there is a canonical reason for a graph to not have countable chromatic number.  Kechris, Solecki, and Todorcevic showed that there is a graph $\mathcal G_0$ such that a Borel graph $\mathcal G$ has $\chi_B(\mathcal G)\leq \aleph_0$ iff there is no continuous (graph) homomorphism from $\mathcal G_0$ to $\mathcal G$.
Proving $\mathcal G_0$ has uncountable Borel chromatic number normally goes via a simple category argument such as in Guest's answer, but as Joel pointed out, this can be seen through a forcing lens if you like.  Proving the dichotomy is normally done using the Gandy-Harrington topology on $2^\mathbb{N}$ (part of an area known as effective descriptive set theory), which doesn't quite admit category arguments.  However, the topology is what's known as strong Choquet (a property based on a certain infinite game), which allows one to carry out something very similar to category arguments.  (It assures you that certain intersections of nonempty open sets are nonempty.)  And of course one can talk instead about the Gandy-Harrington forcing.  More recently, Ben Miller wrote a proof of the $\mathcal G_0$-dichotomy which doesn't use effective descriptive set theory or forcing.
As for $\mathcal G_0$ itself, here's a definition.  Fix a sequence $(t_n)$ of binary sequences such that $|t_n|=n$ and the sequence is dense, meaning for any binary sequence $t$ there is some $n$ such that $t_n$ extends $t$.  (In other words, the basic open sets of $2^\mathbb{N}$ defined by the $t_n$ intersect every open set of $2^\mathbb{N}$.)  Then define $\mathcal G_0$ on $2^\mathbb{N}$ by
$$ x \mathcal G_0 y \Leftrightarrow \exists n [x\restriction n = y\restriction n = t_n \text{ and } x(n)=1-y(n) \text{ and } \forall m>n (x(m)=y(m)) ]$$
I'll note that this is clearly very similar to the graph $G$ in the question, and leave it as an exercise to find a homomorphism from $\mathcal G_0$ to $G$.  I'll also note that while the definition of $\mathcal G_0$ does depend on your choice of $(t_n)$, the KST dichotomy (actually, a slight strengthening of it also due to KST) assures us that any two versions are homeomorphic to subgraphs of each other.
I highly recommend reading the Kechris-Solecki-Todorcevic paper if you have any interest in this topic.  Not only is it the first systematic look at Borel chromatic numbers, it is very readable.  If you'd prefer something more up-to-date, Kechris and Marks have a survey on Borel combinatorics coming soon.  The preprint is available on either of their websites.
A: I claim that there can be no Borel $\mathbb{N}$-coloring of this graph. 
To see this, suppose toward contradiction that there is such a Borel coloring. 
Consider the forcing to add a generic Cohen real, in the form of a
function $g:\mathbb{N}\to\mathbb{N}$. So the forcing conditions
are finite partial functions from $\mathbb{N}\to\mathbb{N}$,
ordered by extension. Since the coloring has a Borel code, we may
interpret this code in the forcing extension $V[g]$ (where I use $V$ here as usual to denote the original set-theoretic universe, rather than your use to denote the underlying set of the graph $\mathbb{N}^{\mathbb{N}}$). Furthermore,
the interpretation of that coloring is still a coloring of the
corresponding graph as defined in the forcing extension $V[g]$,
since the assertion that a given Borel code codes a coloring for
that graph is a $\Pi^1_1$ assertion and hence absolute between the
universe $V$ and the forcing extension $V[g]$. So the generic
function $g$ gets some color, say $k$. This fact must be forced by
some finite piece of the generic function $p=g\upharpoonright n$.
That is, condition $p$ forces that the generic function gets color
$k$. But now let us modify $g$ to form a new function $g'$ by
making a single change beyond $p$. So $g'$ is also generic, and
furthermore extends $p$, and the corresponding forcing extensions
are the same $V[g]=V[g']$. It follows that $g'$ must also get
color $k$, since this was forced by $p$, and this contradicts the
fact that $g$ and $g'$ are adjacent in the graph. So there can be
no such coloring.  QED
This argument is similar to an argument showing that almost-equality has no Borel selector, and a similar idea appears in [this MO question}(https://mathoverflow.net/a/47191/1946) concerning the non-existence of a Borel diagonalization against countable sets of reals.
