# Complexity of relaxed edge colouring

A (proper) $$k$$-edge colouring of a graph $$G(V,E)$$ is a function $$f:E\to\{1,2,\dots,k\}$$ such that adjacent vertices are mapped to different colours; that is, $$f(e)\neq f(e')$$ if $$e$$ and $$e'$$ are incident on the same vertex. It is known that the minimum number of colours required for edge colouring is between $$\Delta(G)$$ and $$\Delta(G)+1$$, and yet it is NP-complete to distinguish between the two cases.

Let us define a relaxed $$k$$-edge colouring of $$G$$ as a function $$f:E\to\{1,2,\dots,k\}$$ such that for every vertex $$v$$ of $$G$$, at most two edges incident on $$v$$ have the same colour.
What is the complexity of relaxed edge colouring?
I am particularly interested in the complexity of relaxed $$k$$-edge colouring for graphs of maximum degree $$k$$.

Edit: The part below was part of the question earlier. But, it is wrong because proper $$k$$-edge colouring and thus relaxed $$k$$-edge colouring are trivially in P for graphs with maximum degree $$k-1$$.

I am particularly interested in the complexity of relaxed $$k$$-edge colouring for graphs of maximum degree $$k-1$$. I have a hunch the problem is going to be computationally hard, which is interesting because $$k$$-edge colouring is polynomial time solvable for the class.

If $$G$$ is $$2k$$-regular, then a relaxed edge coloring with exactly $$k$$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891.
Otherwise, let $$k=\lceil\Delta/2\rceil$$ where $$\Delta$$ is the maximum degree of $$G$$. Then obviously, at least $$k$$ colors are needed in any relaxed coloring of $$G$$. But $$G$$ can be augmented to a $$2k$$-regular graph $$G'$$ (by adding extra vertices and edges if necessary) and any 2-factorization of $$G'$$ restricts to a relaxed edge coloring of $$G$$.
So relaxed edge coloring is easy: the optimal number of colors is always $$\lceil\Delta/2\rceil$$.
• Is this using the same definition of relaxed coloring as the question? My reading of the question is such that $\Delta-1$ colors is the obvious lower bound. Apr 13, 2021 at 22:34