# graphs – 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.

Posted on Categories Articles