Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 @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 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!

share|improve this question
    
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 Feb 19 '13 at 9:13
6  
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) –  vb le Feb 21 '13 at 8:52
    
@vble: thank you! I admit that I wanted "too much". Such an operator would resolve Nishizeki and Zhou 's problem. –  user13136 Feb 22 '13 at 19:00

3 Answers 3

up vote 15 down vote accepted

By analogy with the 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.

share|improve this answer
3  
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 Feb 18 '13 at 9:42
1  
@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 Feb 18 '13 at 17:54
2  
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 Feb 19 '13 at 17:11

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 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.

[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.

share|improve this answer
    
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 Feb 17 '13 at 23:57
    
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 Feb 17 '13 at 23:58
1  
@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 Feb 18 '13 at 13:28
1  
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 Feb 18 '13 at 13:52
1  
@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 Feb 18 '13 at 14:14

(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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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