0
$\begingroup$

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 2 parts, but they are related to each other, so I can not ask each question separately.

Section A

We will mark the maximum degree (of all the vertices of G) in $\Delta$ . Which of the following is the closest bound (or barrier) to the maximum degree of $\widetilde{G}$

  1. $\Delta $
  2. 2$\Delta $ -2
  3. $\Delta ^{2}$
  4. |V|
  5. none of the answers is correct.

I think the answer is 2, if there is a vertex in $G$, with degree $\Delta$. When doing a reduction to $\widetilde{G}$ each edge becomes a vertex, because an edge can be connected to 2 vertices, and these 2 vertices are connected to the other edges, so it makes sense. But I can not rule out the answer 3, because it has a bigger bound(or barrier) and I can not rule out it.

Answer 1 is incorrect, because in my opinion 2 is correct. Answer 4 is incorrect, but fails to explain it logically.

Section B

Recall that the maximum degree $D \leq | V | - 1$. Which of the following is the closest bound (or barrier) to the number of edges in $\widetilde{E}$

  1. $| V | - 1$
  2. $| E | - 1$
  3. $|E| \cdot (| V | - 1)$
  4. $|E|^{2} \cdot | V |$
  5. none of the answers is correct.

I think the answer is 3. If in G there is a complete graph, that all the vertices are connected to all the other vertices, the degree of each vertex is $D = |V|-1$, so in $\widetilde{G}$ there will be up to $|V|-1$ for each vertex of G. The number of vertices in G is |E|, so the answer comes out 3. In my opinion

But I can not say why answer 4. is incorrect.

The question was translated from Hebrew. So I have no source for the question. I have asked a similar question before, but there are other questions here, so I ask again

$\endgroup$
2
  • $\begingroup$ Related: cs.stackexchange.com/q/142541/755 $\endgroup$
    – D.W.
    Oct 26 at 3:39
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Oct 26 at 3:39
2
$\begingroup$

Regarding the first part.

Answer 1 is incorrect. Consider the graph $G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$. The maximum degree of $G$ is $3$ but the degree of $x_{(3,4)}$ in $\widetilde{G}$ is $4$.

Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) is at most $\Delta-1$, therefore the degree of $x_e$ in $\widetilde{G}$ is at most $2(\Delta-1)$.

Answers 3 is incorrect because the question asks for the tightest upper bound and, for $\Delta \ge 1$, $2\Delta -2 = 2(\Delta-1) \le \Delta(\Delta-1) < \Delta^2$.

Answer $4$ is incorrect. Consider the graph $G = (\{1,2,3,4,5\}, \{ (1,2), (1,3), (2,3), (4, 5), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3) \})$. Here $|V|=5$ but the degree of $x_{(4,5)}$ in $\widetilde{G}$ is $6$.

Regarding the second part:

Answer 1 is incorrect, as shown by the second counterexample above.

Answer 2 is incorrect, as shown by the fist counterexample above (the degree of $x_{(1,2)}$ is $2$, the degree of $x_{(1,4)}$ is $4$, $x_{(1,2)}$ and $x_{(1,4)}$ are not neighbors, therefore the number of edge of $\widetilde{G}$ is at least $6$, but $|E|-1=5$).

Answer 3 immediately follows from part $1$. The sum of degrees is $\widetilde{G}$ is at most $|E|(2\Delta - 2)$. Since the number of edges is exactly half the sum of the degrees you get the desired bound.

Answer $4$ is not the tightest bound among the options given since, for graphs with at least one edge, $|E|^2 \cdot |V| > |E|(V-1)$.

$\endgroup$
2
$\begingroup$

Let's check these in reverse order.

  • Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest possible".

  • Question A: You are right that $2\Delta-2$ is the closest bound. Again, other bounds might also be possible, but they are not as tight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.