Different form of edge coloring

Question

This problem actually arose when designing a computer network.

Let $G=(V,E)$ be a finite, 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: x\in e\}$.)

Is there for every graph $G=(V,E)$ with minimal degree $2$ a weak edge coloring $c:E\to\{1,2\}$?

Answer 1

No. For a cycle $C_n$ of odd length the condition is equivalent to bipartiteness of the line graph, which is itself $C_n$ and is not bipartite, hence there is no weak coloring.

Odd cycles are the only counter-examples among connected graphs. To see that, suppose that there is a vertex $v$ of degree at least 3. Add edges of a matching $M$ to $G$ so that in the new graph $G'$ all vertices have even degree. Find an Euler tour in $G'$ starting at $v$ using an edge of $M$ if possible, and color edges of $E \cup M$ alternately in the order of this tour. We claim that the restriction of this coloring to $E$ is weak 2-coloring. If $u \neq v$ had odd degree, then the degree was at least 3, hence the tour visits $u$ at least twice, with adjacent edges having different colors, and deleting at most one edge of $M$ will leave at least one differently colored pair intact. If a vertex $u \neq v$ had even degree in $G$, then no edges incident to $u$ belong to $M$. $v$ has at least one pair of edges of $E$ adjacent in the tour, hence it will not be monochromatic in $E$.

Answer 2

No, an odd cycle is a counterexample. Similarly if there is a component which is an odd cycle. But maybe these are the only cases? (Haha, I forgot to click "save" and Mikhail beat me.)

Ok, wlog $G$ is connected. If all vertices have degree 2, it depends on odd or even length, as above.

The cases where $G$ is a dumbbell or a theta-graph (two vertices with three paths joining them), or a collection of cycles with one common vertex, are easy to colour by ad hoc methods. So suppose $G$ is not one of those. Then there is a path $P$ of (possibly 0) degree 2 vertices between two distinct vertices of degree at least 3. Remove the edges and internal vertices of $P$ and apply induction. Then put back $P$ and easily colour its edges as well.