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.


1 Answer 1


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$.

  • $\begingroup$ 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. $\endgroup$ Commented Apr 13, 2021 at 22:34
  • $\begingroup$ I read it as meaning that at each vertex, there are at most two edges of each color, but maybe it was intended to mean that there is at most a single pair of equal-colored edges and all other edge colors are distinct? That would give the bound you state. $\endgroup$ Commented Apr 13, 2021 at 22:39

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.