# Are all infinite graphs $3$-weak-edge colorable?

Let $G=(V,E)$ be a simple, undirected graph such that every vertex has degree at least $2$. Given $n\in\mathbb{N}$, a map $c:E \to \{1,\ldots, n\}$ is said to be a weak coloring if for every $v\in V$ the edges adjacent to $v$ do not all have the same color. (More formally, we want the restriction $c|_{E(v)}$ to be non-constant, where $E(v) = \{e\in E: v\in e\}$.)

These two nice posts by Mikail Tikhomirov and Brendan McKay respectively show that for every finite graph there is a weak edge coloring with $3$ colors. I tried to carry through their arguments with transfinite induction to infinite graphs - without success.

Question. If $G=(V,E)$ is an infinite simple undirected graph, is there a weak edge coloring $c:E \to \{1,2,3\}$?

• It looks like any connected component which is not an odd cycle (in particular, any infinite component) admits such a coloring with 2 colors. – Fedor Petrov Nov 5 '17 at 13:26

If $E$ is countable, then we can define the function $c$ by induction as follows. Choose an identification $E = \{1,2,\ldots\}$ and choose $c(1) \in \{1,2,3\}$ arbitrarily. Assume that $c(k)$ is defined for every $k < n$. Let $v$ and $v'$ denote the ends of $n$ and let $E(v)$ (resp. $E(v')$) be the edges containing $v$ (resp. $v'$). There are at most two forbidden colors for $n$: if edges in $E(v)$ which have already been colored have the same colour $i_v$, then $i_v$ is possibly a forbidden color. Same for $v'$ and we have another possibly forbidden color $i_{v'}$. Choose $c(n) \in \{1,2,3\} \backslash \{i_v, i_{v'}\}$.
• Then there's no $i_v$. – HYL Nov 5 '17 at 11:21
• @DominicvanderZypen Doesn't this nice argument prove more: that the edges of any graph (finite or infinite, countable or uncountable) can be colored with three colors so that for any vertex $v:$ (1) if $v$ has finite degree $d$ then no color occurs on more than $\lceil d/2\rceil$ of the edges incident with $v;$ and (2) if $v$ has infinite degree than at least two colors occur on infinitely many of the edges incident with $v?$ – bof Nov 5 '17 at 21:32
• @DominicvanderZypen This construction shows that, for any integer $k\ge0,$ the edges of any graph $G$ can be colored with $2k+1$ colors so that, for each vertex $v,$ there are edges of at least $\min\{\deg(v),\ k+1\}$ different colors incident with $v.$ – bof Nov 7 '17 at 10:22
Wlog $G$ is connected. Let $T\subseteq G$ be a spanning tree. Choose a vertex $r$ in $T$ with dgeree at least 2, make it the root. Split the neighbors of $r$ into two nonempty sets, $A$ and $B$. Color all tree edges between $r$ and $A$, blue, those between $r$ and $B$ red. Then continue coloring the edges of $T$: those from $A$ red, from $B$ blue, etc. Eventually all edges of $T$ are colored with red and blue. Finally color the remaining edges with green. This is good: all nonleaf vertices of $T$ have colors red and blue, the leaf vertices necessarily have a red/blue colored edge in $T$, and another in $G-T$, colored green.