# edge-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve.

That's the problem:

Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "Is there a coloration in arcs of G which uses at most k colors?". While painting vertices to two neighboring vertices must not have the same color, painting arcs to two neighboring arcs (i.e., having a common vertex) must not be The same color. That is, the language is: Edge-Coloring = {<G,k>|G can be arcuated by coloring using ≤ k colors} Let's look at reduction, Edge-Coloring $$\leq _p$$ Vertex-Coloring According to the graph G = (V, E), built new vertices Group: $$\widetilde{V}$$ = {$$x_e | e \in E$$} We will define a new edge between two vertices, $$x_{e_1}$$ and $$x_{e_2}$$, if there is a common vertex between edges $$e_1$$ and $$e_2$$. $$\widetilde{E}$$ = {$$(x_{e_1},x_{e_2}) | e_1 \cap e_2 \neq \phi$$} Finally we will define: $$\widetilde{G}$$ = ($$\widetilde{V}$$ , $$\widetilde{E}$$)

The question has 3 parts, but they are related to each other, so I can not ask each question separately.

Section A

If the G edges can be painted in k colors, in how many colors the vertices can be painted in $$\widetilde{G}$$

1. k
2. 3k
3. k^2
4. |V|+1
5. none of the answers is correct.

I think the correct answer is k, in graph G we have to color the edges, every edge in G becomes a vertex in  $$\widetilde{G}$$, and every vertex in G becomes an edge in $$\widetilde{G}$$, which means there is symmetry. If in G the edges need to be painted in K colors then in  $$\widetilde{G}$$ the vertices need to be painted in K colors

Section B

Is this a polynomial reduction?

1. yes.
2. No, the amount of edges may be quadratic as a function of the amount of vertices.
3. No, the amount of edges may be exponential as a function of the amount of vertices.
4. You can not tell, depending on the size of the graph
5. none of the answers is correct.

I think the correct answer is Yes , Each adge in G becomes a vertex in  $$\widetilde{G}$$ , a polynomial runtime as the size of the | E |. After this each edge in E can be connected to 2 vertices, and each vertex can be connected to all the other edges. For each edge we will check if it is connected to the other edges, running time of | E |^2.

Section C Is the reduction correct and well defined?

1. Yes, reduction correct and well defined
2. Although the reduction is correct, but it does not deal with cases where the original graph G was empty (without edges)
3. Although the reduction is well defined for all graphs, it is incorrect when the number of edges is evaluated as a function of the number of vertices.
4. No
5. none of the answers is correct.

I feel like the answer is 1., but I have no explanation for it, here I actually think I'm stuck. How can you check that reduction correct and well defined?

I think this is a very easy question, but I could not answer it, thank you very much.

The question was translated from Hebrew. So I have no source for the question.

• – Juho
Jul 22 at 8:32
• – D.W.
Oct 26 at 3:39
• You can still credit the original source: e.g., a book, a specific class, a web page. Nothing about translating from another language prevents you from crediting your sources.
– D.W.
Oct 26 at 3:39

To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $$G$$ of Edge-Coloring has a solution precisely when the instance $$G'$$ of Vertex-Coloring has a solution.

Let's consider the questions A, B and C:

• Question A: You should have a look at my answer to question C here first. Your intuition looks promising, but you should formalize (i.e., prove) it.

• Question B: You are correct, the reduction is easily doable in polynomial time.

• Question C: The construction is describing the construction of the line graph of $$G$$. Your task is to prove that $$G$$ has an edge $$k$$-coloring if and only if $$G'$$ has a vertex $$k$$-coloring. Do this in two parts: given an edge $$k$$-coloring of $$G$$, show how you can build a vertex $$k$$-coloring for $$G'$$. Then show the reverse direction, i.e., that a vertex $$k$$-coloring for $$G'$$ gives you an edge $$k$$-coloring for $$G$$. This is a good exercise, so I won't ruin (all) the details for you. Hint: in the first direction, start by giving the vertices $$x_e$$ the color on $$e$$. In the reverse reduction, what can you say about the coloring if you restrict it to the vertices $$x_e$$, i.e., what does this imply for the edges $$e$$ in $$G$$?

If you feel stuck, look at examples of some other reductions to get the idea.

• I think I was able to prove it, and it turned out that the reduction is correct, I tried to produce all kinds of graphs, and each time I managed to paint the 2 types of graphs in the same k colors. Formally I could not prove, I did not find a source in the books and on the Internet. I think the reduction is correct and it is possible to paint both graphs in k colors, am I right? Jul 22 at 13:38
• @anihaham Here's the proof that if $G$ can be edge-colored in $k$ colors, then $G'$ can be vertex-colored in $k$ colors. Let $c$ be a proper edge $k$-coloring. Our goal is to build a proper vertex-coloring using $k$ colors, say $c'$. My hint says that let's make $c'$ so that $c'(x_e) = c(e)$, i.e., we assign the color from the edge in $G$ to the corresponding vertex of $G'$. By construction, any vertex $v$ in $G'$ is adjacent precisely to the edges it's incident to in $G$ and these are all colored in distinct colors. Thus, $v$ is colored distinctly from its neighbors and we are done.
– Juho
Jul 22 at 14:01