<p>The question contains some ambiguity in what you mean by “vertex colorings of a graph <i>G</i> are edge colorings of a graph <i>H</i>,” but it is NP-hard to construct a graph whose edge chromatic number is equal to the (vertex) chromatic number of a given graph.  Formally, the following relation problem is NP-hard.</p>

<p><strong>Representing chromatic number as edge chromatic number</strong><br>
<em>Instance</em>: A graph <i>G</i>.<br>
<em>Solution</em>: A graph <i>H</i> such that the edge chromatic number χ’(<i>H</i>) of <i>H</i> is equal to the chromatic number χ(<i>G</i>) of <i>G</i>.</p>

<p>This is because <a href="http://en.wikipedia.org/wiki/Vizing%27s_theorem">Vizing’s theorem</a> gives a (trivial) efficient algorithm which approximates the edge chromatic number within an additive error of 1 whereas the chromatic number is hard even to approximate in various senses.  For example, Khanna, Linial, and Safra [KLS00] showed that the following problem is NP-complete (and later Guruswami and Khanna [GK04] gave a much simpler proof):</p>

<p><strong>3-colorable versus non-4-colorable</strong><br>
<em>Instance</em>: A graph <i>G</i>.<br>
<em>Yes-promise</em>: <i>G</i> is 3-colorable.<br>
<em>No-promise</em>: <i>G</i> is not 4-colorable.</p>

<p>This result is sufficient to prove the NP-hardness that I claimed at the beginning.  A proof is left as an exercise, but here is a hint:</p>

<blockquote>
  <p><strong>Exercise</strong>.  Prove that the aforementioned problem “Representing chromatic number as edge chromatic number” is NP-hard under polynomial-time functional reducibility by reducing “3-colorable versus non-4-colorable” to it.  That is, construct two polynomial-time functions <i>f</i> (which maps a graph to a graph) and <i>g</i> (which maps a graph to a bit) such that</p>
  
  <ul>
  <li>If <i>G</i> is a 3-colorable graph and <i>H</i> is a graph such that χ(<i>f</i>(<i>G</i>))=χ’(<i>H</i>), then <i>g</i>(<i>H</i>)=1.</li>
  <li>If <i>G</i> is a non-4-colorable graph and <i>H</i> is a graph such that χ(<i>f</i>(<i>G</i>))=χ’(<i>H</i>), then <i>g</i>(<i>H</i>)=0.</li>
  </ul>
</blockquote>

<h3>References</h3>

<p>[GK04] Venkatesan Guruswami and Sanjeev Khanna.  On the hardness of 4-coloring a 3-colorable graph.  <em>SIAM Journal on Discrete Mathematics</em>, 18(1):30–40, 2004.  DOI: <a href="http://dx.doi.org/10.1137/S0895480100376794">10.1137/S0895480100376794</a>.</p>

<p>[KLS00] Sanjeev Khanna, Nathan Linial, and Shmuel Safra.  On the hardness of approximating the chromatic number.  <em>Combinatorica</em>, 20(3):393–415, March 2000.  DOI: <a href="http://dx.doi.org/10.1007/s004930070013">10.1007/s004930070013</a>.</p>

CC BY-SA 3.0
2013-02-17T23:57:45.843Z
Thank you for reply!  
 I am a little bit imprecise by formulating “vertex colorings of a graph $G$ *are* edge colorings of a
 graph $H$”. What I mean is an operator $\Phi$ like the line graph operator $L$, but from vertex 
colourings to edge colourings. This is somehow more than  $\chi(G) = \chi'(H)$.
user13136
CC BY-SA 3.0
2013-02-17T23:58:14.267Z
Since VERTEX COLOURING and EDGE COLOURING are both $\mathsf{NP}$-complete, 
we can construct, by definition, $H$ from $G$ in polynomial time such that 
$\chi(G) \le k$ iff $\chi'(H) \le k'$.But such a construction need not fulfill the property for an 
operator $\Phi$ I am looking for. It only reduces vertex colourings to edge colourings.
user13136
CC BY-SA 3.0
2013-02-18T01:34:41.533Z
@user13136: I am not sure why you wrote your second comment.  As you wrote, the fact that the vertex coloring is reducible to the edge coloring is a direct consequence of both problems being NP-complete, and has nothing to do with your question or my answer.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-18T05:52:08.797Z
Do you mean that you want the family of vertex colorings of $G$ to be bijectively mapped to the family of edge colorings of $\Phi(G)$?
Yoshio Okamoto
CC BY-SA 3.0
2013-02-18T09:25:35.490Z
My comment above should have been directed to @user13136.
Yoshio Okamoto
CC BY-SA 3.0
2013-02-18T09:33:15.187Z
@Tsuyoshi Ito: My second comment was the reason why I am interested in finding an operator that can be constructed in polynomial time (cf. also Remark in my question about stable sets and matchings).
user13136
CC BY-SA 3.0
2013-02-18T09:40:56.693Z
@YoshioOkamoto: Yes, you are right. Like edge colourings and vertex colourings between $G$ and $L(G)$.
user13136
CC BY-SA 3.0
2013-02-18T12:53:07.037Z
@user13136: I do not know if you understand this, but I already showed that a weaker requirement than what you asked is impossible unless P=NP.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-18T13:20:12.113Z
@TsuyoshiIto: I think I understand your answer and maybe in this case you are right. But it is not clear for me if a problem still remains difficult under stronger/weaker requirements. Consider e.g. COLOURING for planar graphs. With 3 colours the problem is hard, with 2 or 4 it becomes easy.
user13136
CC BY-SA 3.0
2013-02-18T13:28:50.483Z
@user13136: If a weaker requirement is impossible to satisfy, the stronger requirement is obviously also impossible.  This is logic.  You should understand that your planar graph example is not a counterexample to this.  Deciding the 3-colorability of a given planar graph is _not_ a weaker requirement than deciding the 4-colorability of a given planar graph; they are just different requirements.  On the other hand, I already showed that what you want is impossible unless P=NP, period.  But if you have trouble understanding this, I do not think there is anything I can do to help you understand.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-18T13:52:05.903Z
If I understand the question correctly, such a map $\Phi$ doesn't exist. We don't need to refer to NP-completeness. Just consider $G=K_{1,3}$ and suppose such $\Phi(G)$ exists. Since $G$ is 2-colorable, $\Phi(G)$ should be 2-edge-colorable. This means the maximum degree of $\Phi(G)$ is at most two. Since $\Phi(G)$ has four edges, we can go through all candidates for $\Phi(G)$ (seven candidates up to isomorphism), and we will find that the family of edge colorings of $\Phi(G)$ and the family of vertex colorings of $G$ are different. A contradiction.
Yoshio Okamoto
CC BY-SA 3.0
2013-02-18T14:05:23.307Z
@Yoshio: I think that that is essentially what usul wrote in the answer.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-18T14:08:57.140Z
@TsuyoshiIto: I missed to find usul's answer. Thank you.
Yoshio Okamoto
CC BY-SA 3.0
2013-02-18T14:14:17.030Z
@user13136: It occurred to me that you might have been confused because I wrote only a proof idea and I left out the actual proof.  I revised the answer so that it would be clear that I left out the actual proof, and added some hints for proof.  If this still does not work for you, then I will give up.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-17T22:40:25.253Z
2013-02-18T17:15:30.733Z
2013-02-18T17:15:30.733Z
Tsuyoshi Ito
<p>(This is an addition to usul's answer and YoshioOkamoto's comment, rather than an answer.) It can be seen that your operation $\Phi$ exists only for those graphs $G$ for which there is a graph $G'$ with $G = L(G')$, i.e. $G$ is a line graph (checkable in polytime). In this case, $\Phi$ is the "inverse line graph operator" $L^{-1}$, i.e. $\Phi(G)=G'$, and vertex colorings of $G$ are edge colorings of $\Phi(G)$. </p>

CC BY-SA 3.0
2013-02-25T11:18:12.277Z
2013-02-25T11:18:12.277Z
In Theory
<p>By analogy with the <a href="http://en.wikipedia.org/wiki/Line_graph">line graph</a>, I think you are asking the following:</p>

<blockquote>
  <p>For every undirected graph $G = (V,E)$, does there exist an undirected graph $G' = (V',E')$ such that each vertex $v \in V$ corresponds to an edge $(v_1,v_2) \in E'$ and the edges corresponding to $u \in V$ and $v \in V$ share at least one endpoint if and only if $(u,v) \in E$?</p>
</blockquote>

<p>The answer can be seen to be <em>no</em>. Consider the four-vertex tree $G$ with root $v$ having three children $x,y,z$. In $G'$, we must have four edges: $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$. Further, it must be the case that either $v_1$ or $v_2$ is an endpoint of each of the other three edges (<em>i.e.</em>, $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$, etc). But this means that at least two of the other three edges must share a common endpoint, which violates our requirements since no two of $x,y,z$ are adjacent in the original graph.</p>

<p>I think the same graph will give you a counterexample for the matching question as well.</p>

CC BY-SA 3.0
2013-02-18T09:42:42.917Z
Good point! Actually I had the same thoughts. But maybe there is another way for defining $G'$? Or how can we formally prove that such an operator $\Phi$ does not exist?
user13136
CC BY-SA 3.0
2013-02-18T17:54:26.857Z
@user13136, hmm, maybe there is some creative way around it, but you would need to rephrase your question (I think my counterexample is a formal proof for the question as phrased in the quoted box). Intuitively, I think the problem is that when going the line-graph direction, we take an edge (that can only be connected to two vertices) and turn it into a vertex (that can be connected to any number of edges) -- easy. The reverse is opposite and harder.
usul
CC BY-SA 3.0
2013-02-19T17:11:33.187Z
Just adding to usul's answer, the short answer is no, because matchings have structural properties not necessarily present in stable sets.  For example, every line graph is also quasi-line and claw-free; this really limits the depth of edge colourings compared to vertex colourings.
Andrew D. King
CC BY-SA 3.0
2013-02-18T04:47:45.540Z
2013-02-18T04:47:45.540Z
usul
<p>We know that edge colourings of a graph $G$ <em>are</em> vertex colourings of a special graph, 
namely of the line graph $L(G)$ of $G$. </p>

<p>Is there a graph operator $\Phi$ such that vertex colourings of a graph $G$ <em>are</em> 
edge colourings of the graph $\Phi(G)$ ? 
I am interested in such a graph operator that can be constructed in polynomial time, 
i.e. the graph  $\Phi(G)$ can be obtained from $G$ in polynomial time. </p>

<p><em>Remark</em>:  Similar question can be asked for stable sets and matchings. A matching 
in $G$ is a stable set in $L(G)$. Is there a graph operator $\Psi$ such that stable sets 
in $G$ are matchings in $\Psi(G)$? 
Since STABLE SET is $\mathsf{ NP}$-complete and MATCHING belongs to $ \mathsf{P}$, such a 
graph operator $\Psi$ (if exists) cannot be constructed in polynomial time, assuming 
$\mathsf{NP}\not=\mathsf{P}$.  </p>

<p>EDIT: Inspired by @usul's answer and @Okamoto's and @King's comments, I found a weaker form for my problem: Vertex colourings of a graph $G$ are edge colourings of a <em>hypergraph</em> $\Phi(G)$ defined as follows. The vertex set of $\Phi(G)$ is the same
vertex set of $G$. For each vertex $v$ of $G$, the closed neighbourhood $N_G[v]= N_G(v) \cup\{v\}$ is an edge of the hypergraph $\Phi(G)$. Then $G$ is the line graph of the hypergraph $\Phi(G)$ and therefore vertex colourings of $G$ are edge colourings of $\Phi(G)$. </p>

<p>Again, I am grateful for all answers and comments showing that, with or without assuming $\mathsf{NP}\not=\mathsf{P}$, the operator I am looking for cannot exist. It would be nice if I could accept all the answers!</p>

CC BY-SA 3.0
2013-02-19T09:13:27.423Z
Thanks all for kind comments (and patience!) and useful answers. I need time to read, to think and might possibly come back with fresh eyes.
user13136
CC BY-SA 3.0
2013-02-21T08:52:30.547Z
I came across the following quite interesting problem  
posed by Nishizeki and Zhou in 1998 that is somehow related to your question and your second comment to @TsuyoshiIto: 

  **Can the vertex-coloring problem be “simply” reduced to the edge-coloring problem?** (...) Since both 
  problems are NP-complete, either can be reduced to the other plausibly through 3-SAT, due to the theory of 
  NP-completeness. Thus the open problem asks, ... (see [here](http://www.dagstuhl.de/Reports/96/9620.pdf))
vb le
CC BY-SA 3.0
2013-02-22T19:00:38.513Z
@vble: thank you! I admit that I wanted "too much". Such an operator would resolve Nishizeki and Zhou 's problem.
user13136
<graph-theory><graph-algorithms>
Are vertex colourings--in a sense--edge colourings?
user13136
# Are vertex colourings--in a sense--edge colourings?

(Asked by: username_0 on 2013-02-17)

We know that edge colourings of a graph $G$ *are* vertex colourings of a special graph,
namely of the line graph $L(G)$ of $G$.

Is there a graph operator $\Phi$ such that vertex colourings of a graph $G$ *are*
edge colourings of the graph $\Phi(G)$ ?
I am interested in such a graph operator that can be constructed in polynomial time,
i.e. the graph $\Phi(G)$ can be obtained from $G$ in polynomial time.

*Remark*: Similar question can be asked for stable sets and matchings. A matching
in $G$ is a stable set in $L(G)$. Is there a graph operator $\Psi$ such that stable sets
in $G$ are matchings in $\Psi(G)$?
Since STABLE SET is $\mathsf{ NP}$-complete and MATCHING belongs to $ \mathsf{P}$, such a
graph operator $\Psi$ (if exists) cannot be constructed in polynomial time, assuming
$\mathsf{NP}\not=\mathsf{P}$.

EDIT: Inspired by @username_5's answer and @Okamoto's and @King's comments, I found a weaker form for my problem: Vertex colourings of a graph $G$ are edge colourings of a *hypergraph* $\Phi(G)$ defined as follows. The vertex set of $\Phi(G)$ is the same
vertex set of $G$. For each vertex $v$ of $G$, the closed neighbourhood $N\_G[v]= N\_G(v) \cup\{v\}$ is an edge of the hypergraph $\Phi(G)$. Then $G$ is the line graph of the hypergraph $\Phi(G)$ and therefore vertex colourings of $G$ are edge colourings of $\Phi(G)$.

Again, I am grateful for all answers and comments showing that, with or without assuming $\mathsf{NP}\not=\mathsf{P}$, the operator I am looking for cannot exist. It would be nice if I could accept all the answers!

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_0**: Thanks all for kind comments (and patience!) and useful answers. I need time to read, to think and might possibly come back with fresh eyes.  
> **username_1**: I came across the following quite interesting problem   posed by Nishizeki and Zhou in 1998 that is somehow related to your question and your second comment to @TsuyoshiIto:     **Can the vertex-coloring problem be “simply” reduced to the edge-coloring problem?** (...) Since both    problems are NP-complete, either can be reduced to the other plausibly through 3-SAT, due to the theory of    NP-completeness. Thus the open problem asks, ... (see [here](http://www.dagstuhl.de/Reports/96/9620.pdf))  
> **username_0**: @vble: thank you! I admit that I wanted "too much". Such an operator would resolve Nishizeki and Zhou 's problem.  

---

## 3 answers

### Answer by username_5 on 2013-02-18. Score: 16 | Accepted answer

By analogy with the [line graph](http://en.wikipedia.org/wiki/Line_graph), I think you are asking the following:

> For every undirected graph $G = (V,E)$, does there exist an undirected graph $G' = (V',E')$ such that each vertex $v \in V$ corresponds to an edge $(v\_1,v\_2) \in E'$ and the edges corresponding to $u \in V$ and $v \in V$ share at least one endpoint if and only if $(u,v) \in E$?

The answer can be seen to be *no*. Consider the four-vertex tree $G$ with root $v$ having three children $x,y,z$. In $G'$, we must have four edges: $(v\_1,v\_2),(x\_1,x\_2),(y\_1,y\_2),(z\_1,z\_2)$. Further, it must be the case that either $v\_1$ or $v\_2$ is an endpoint of each of the other three edges (*i.e.*, $\left| \{v\_1,v\_2\} \cap \{x\_1,x\_2\} \right| \geq 1$, etc). But this means that at least two of the other three edges must share a common endpoint, which violates our requirements since no two of $x,y,z$ are adjacent in the original graph.

I think the same graph will give you a counterexample for the matching question as well.

> **Comments:**
> **username_0**: Good point! Actually I had the same thoughts. But maybe there is another way for defining $G'$? Or how can we formally prove that such an operator $\Phi$ does not exist?  
> **username_5**: @username_0, hmm, maybe there is some creative way around it, but you would need to rephrase your question (I think my counterexample is a formal proof for the question as phrased in the quoted box). Intuitively, I think the problem is that when going the line-graph direction, we take an edge (that can only be connected to two vertices) and turn it into a vertex (that can be connected to any number of edges) -- easy. The reverse is opposite and harder.  
> **username_6**: Just adding to username_5's answer, the short answer is no, because matchings have structural properties not necessarily present in stable sets.  For example, every line graph is also quasi-line and claw-free; this really limits the depth of edge colourings compared to vertex colourings.  

---

### Answer by username_2 on 2013-02-17. Score: 14

The question contains some ambiguity in what you mean by “vertex colorings of a graph *G* are edge colorings of a graph *H*,” but it is NP-hard to construct a graph whose edge chromatic number is equal to the (vertex) chromatic number of a given graph. Formally, the following relation problem is NP-hard.

**Representing chromatic number as edge chromatic number**  
*Instance*: A graph *G*.  
*Solution*: A graph *H* such that the edge chromatic number χ’(*H*) of *H* is equal to the chromatic number χ(*G*) of *G*.

This is because [Vizing’s theorem](http://en.wikipedia.org/wiki/Vizing%27s_theorem) gives a (trivial) efficient algorithm which approximates the edge chromatic number within an additive error of 1 whereas the chromatic number is hard even to approximate in various senses. For example, Khanna, Linial, and Safra [KLS00] showed that the following problem is NP-complete (and later Guruswami and Khanna [GK04] gave a much simpler proof):

**3-colorable versus non-4-colorable**  
*Instance*: A graph *G*.  
*Yes-promise*: *G* is 3-colorable.  
*No-promise*: *G* is not 4-colorable.

This result is sufficient to prove the NP-hardness that I claimed at the beginning. A proof is left as an exercise, but here is a hint:

> **Exercise**. Prove that the aforementioned problem “Representing chromatic number as edge chromatic number” is NP-hard under polynomial-time functional reducibility by reducing “3-colorable versus non-4-colorable” to it. That is, construct two polynomial-time functions *f* (which maps a graph to a graph) and *g* (which maps a graph to a bit) such that
>
> * If *G* is a 3-colorable graph and *H* is a graph such that χ(*f*(*G*))=χ’(*H*), then *g*(*H*)=1.
> * If *G* is a non-4-colorable graph and *H* is a graph such that χ(*f*(*G*))=χ’(*H*), then *g*(*H*)=0.

### References

[GK04] Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. *SIAM Journal on Discrete Mathematics*, 18(1):30–40, 2004. DOI: [10.1137/S0895480100376794](http://dx.doi.org/10.1137/S0895480100376794).

[KLS00] Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. *Combinatorica*, 20(3):393–415, March 2000. DOI: [10.1007/s004930070013](http://dx.doi.org/10.1007/s004930070013).

> **Comments:**
> **username_0**: Thank you for reply!    I am a little bit imprecise by formulating “vertex colorings of a graph $G$ *are* edge colorings of a  graph $H$”. What I mean is an operator $\Phi$ like the line graph operator $L$, but from vertex  colourings to edge colourings. This is somehow more than  $\chi(G) = \chi'(H)$.  
> **username_0**: Since VERTEX COLOURING and EDGE COLOURING are both $\mathsf{NP}$-complete,  we can construct, by definition, $H$ from $G$ in polynomial time such that  $\chi(G) \le k$ iff $\chi'(H) \le k'$.But such a construction need not fulfill the property for an  operator $\Phi$ I am looking for. It only reduces vertex colourings to edge colourings.  
> **username_2**: @username_0: I am not sure why you wrote your second comment.  As you wrote, the fact that the vertex coloring is reducible to the edge coloring is a direct consequence of both problems being NP-complete, and has nothing to do with your question or my answer.  
> **username_3**: Do you mean that you want the family of vertex colorings of $G$ to be bijectively mapped to the family of edge colorings of $\Phi(G)$?  
> **username_3**: My comment above should have been directed to @username_0.  
> **username_0**: @username_2: My second comment was the reason why I am interested in finding an operator that can be constructed in polynomial time (cf. also Remark in my question about stable sets and matchings).  
> **username_0**: @YoshioOkamoto: Yes, you are right. Like edge colourings and vertex colourings between $G$ and $L(G)$.  
> **username_2**: @username_0: I do not know if you understand this, but I already showed that a weaker requirement than what you asked is impossible unless P=NP.  
> **username_0**: @TsuyoshiIto: I think I understand your answer and maybe in this case you are right. But it is not clear for me if a problem still remains difficult under stronger/weaker requirements. Consider e.g. COLOURING for planar graphs. With 3 colours the problem is hard, with 2 or 4 it becomes easy.  
> **username_2**: @username_0: If a weaker requirement is impossible to satisfy, the stronger requirement is obviously also impossible.  This is logic.  You should understand that your planar graph example is not a counterexample to this.  Deciding the 3-colorability of a given planar graph is _not_ a weaker requirement than deciding the 4-colorability of a given planar graph; they are just different requirements.  On the other hand, I already showed that what you want is impossible unless P=NP, period.  But if you have trouble understanding this, I do not think there is anything I can do to help you understand.  
> **username_3**: If I understand the question correctly, such a map $\Phi$ doesn't exist. We don't need to refer to NP-completeness. Just consider $G=K_{1,3}$ and suppose such $\Phi(G)$ exists. Since $G$ is 2-colorable, $\Phi(G)$ should be 2-edge-colorable. This means the maximum degree of $\Phi(G)$ is at most two. Since $\Phi(G)$ has four edges, we can go through all candidates for $\Phi(G)$ (seven candidates up to isomorphism), and we will find that the family of edge colorings of $\Phi(G)$ and the family of vertex colorings of $G$ are different. A contradiction.  
> **username_2**: @Yoshio: I think that that is essentially what username_5 wrote in the answer.  
> **username_3**: @TsuyoshiIto: I missed to find username_5's answer. Thank you.  
> **username_2**: @username_0: It occurred to me that you might have been confused because I wrote only a proof idea and I left out the actual proof.  I revised the answer so that it would be clear that I left out the actual proof, and added some hints for proof.  If this still does not work for you, then I will give up.  

---

### Answer by username_4 on 2013-02-25. Score: 9

(This is an addition to username_5's answer and YoshioOkamoto's comment, rather than an answer.) It can be seen that your operation $\Phi$ exists only for those graphs $G$ for which there is a graph $G'$ with $G = L(G')$, i.e. $G$ is a line graph (checkable in polytime). In this case, $\Phi$ is the "inverse line graph operator" $L^{-1}$, i.e. $\Phi(G)=G'$, and vertex colorings of $G$ are edge colorings of $\Phi(G)$.


---

