<p>If <span class="math-container">$G$</span> is <span class="math-container">$2k$</span>-regular, then a relaxed edge coloring with exactly <span class="math-container">$k$</span> colors is the same thing as a <a href="https://en.wikipedia.org/wiki/Graph_factorization" rel="noreferrer">2-factorization</a>, and is known to always exist by results of Petersen 1891.</p>
<p>Otherwise, let <span class="math-container">$k=\lceil\Delta/2\rceil$</span> where <span class="math-container">$\Delta$</span> is the maximum degree of <span class="math-container">$G$</span>. Then obviously, at least <span class="math-container">$k$</span> colors are needed in any relaxed coloring of <span class="math-container">$G$</span>. But <span class="math-container">$G$</span> can be augmented to a <span class="math-container">$2k$</span>-regular graph <span class="math-container">$G'$</span> (by adding extra vertices and edges if necessary) and any 2-factorization of <span class="math-container">$G'$</span> restricts to a relaxed edge coloring of <span class="math-container">$G$</span>.</p>
<p>So relaxed edge coloring is easy: the optimal number of colors is always <span class="math-container">$\lceil\Delta/2\rceil$</span>.</p>

CC BY-SA 4.0
2021-04-13T22:34:34.963Z
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.
Ben Reiniger
CC BY-SA 4.0
2021-04-13T22:39:44.637Z
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.
David Eppstein
CC BY-SA 4.0
2021-04-13T07:42:31.517Z
2021-04-13T07:42:31.517Z
David Eppstein
<p>A (proper) <span class="math-container">$k$</span>-edge colouring of a graph <span class="math-container">$G(V,E)$</span> is a function <span class="math-container">$f:E\to\{1,2,\dots,k\}$</span> such that adjacent vertices are mapped to different colours; that is, <span class="math-container">$f(e)\neq f(e')$</span> if <span class="math-container">$e$</span> and <span class="math-container">$e'$</span> are incident on the same vertex. It is known that the minimum number of colours required for edge colouring is between <span class="math-container">$\Delta(G)$</span> and <span class="math-container">$\Delta(G)+1$</span>, and yet it is NP-complete to distinguish between the two cases.</p>
<p>Let us define a relaxed <span class="math-container">$k$</span>-edge colouring of <span class="math-container">$G$</span> as a function <span class="math-container">$f:E\to\{1,2,\dots,k\}$</span> such that for every vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>, at most two edges incident on <span class="math-container">$v$</span> have the same colour.<br />
<strong>What is the complexity of relaxed edge colouring?</strong><br />
I am particularly interested in the complexity of relaxed <span class="math-container">$k$</span>-edge colouring for graphs of maximum degree <span class="math-container">$k$</span>.</p>
<p>Edit: The part below was part of the question earlier. But, it is wrong because proper <span class="math-container">$k$</span>-edge colouring and thus relaxed <span class="math-container">$k$</span>-edge colouring are trivially in P for graphs with maximum degree <span class="math-container">$k-1$</span>.</p>
<blockquote>
<p>I am particularly interested in the complexity of relaxed <span class="math-container">$k$</span>-edge
colouring for graphs of maximum degree <span class="math-container">$k-1$</span>. I have a hunch the
problem is going to be computationally hard, which is interesting
because <span class="math-container">$k$</span>-edge colouring is polynomial time solvable for the class.</p>
</blockquote>

<cc.complexity-theory><graph-theory><np-hardness><graph-colouring>
Complexity of relaxed edge colouring
Cyriac Antony
# Complexity of relaxed edge colouring

(Asked by: username_0 on 2021-04-13)

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.

**Tags:** cc.complexity-theory, graph-theory, np-hardness, graph-colouring

---

## 1 answers

### Answer by username_1 on 2021-04-13. Score: 5 | Accepted answer

If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a [2-factorization](https://en.wikipedia.org/wiki/Graph_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$.

> **Comments:**
> **username_2**: 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.  
> **username_1**: 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.  

---

