5
$\begingroup$

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\}$?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It looks like any connected component which is not an odd cycle (in particular, any infinite component) admits such a coloring with 2 colors. $\endgroup$
    – Fedor Petrov
    Nov 5, 2017 at 13:26

2 Answers 2

Reset to default
7
$\begingroup$

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'}\}$.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Then there's no $i_v$. $\endgroup$
    – HYL
    Nov 5, 2017 at 11:21
  • 4
    $\begingroup$ I think this argument can be generalized to transfinite induction. The only thing we could possibly have to take care of is that at limit stages we won't have all edges around one vertex colored the same, but this is guaranteed by the construction: if there are two or more edges already colored, there will be two of different colors. $\endgroup$
    – Wojowu
    Nov 5, 2017 at 11:33
  • $\begingroup$ Thanks to both of you! I think with HYL's argument and @Wojowu's remark I can carry through the transfinite induction. $\endgroup$
    – Dominic van der Zypen
    Nov 5, 2017 at 15:38
  • $\begingroup$ @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?$ $\endgroup$
    – bof
    Nov 5, 2017 at 21:32
  • $\begingroup$ @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.$ $\endgroup$
    – bof
    Nov 7, 2017 at 10:22
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Brilliant, thanks for this additional answer! $\endgroup$
    – Dominic van der Zypen
    Nov 12, 2017 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.