16

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!

user13136
  • 2,477
  • 1
  • 24
  • 24
  • 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 09: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 08: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 Answers3

16

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.

usul
  • 7,615
  • 1
  • 26
  • 45
  • 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 09: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
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 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.

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • 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
  • @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 Feb 18 '13 at 01:34
  • 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 Feb 18 '13 at 05:52
  • My comment above should have been directed to @user13136. – Yoshio Okamoto Feb 18 '13 at 09:25
  • @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 Feb 18 '13 at 09:33
  • @YoshioOkamoto: Yes, you are right. Like edge colourings and vertex colourings between $G$ and $L(G)$. – user13136 Feb 18 '13 at 09:40
  • @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 Feb 18 '13 at 12:53
  • @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 Feb 18 '13 at 13:20
  • 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
  • @Yoshio: I think that that is essentially what usul wrote in the answer. – Tsuyoshi Ito Feb 18 '13 at 14:05
  • @TsuyoshiIto: I missed to find usul's answer. Thank you. – Yoshio Okamoto Feb 18 '13 at 14:08
  • 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
9

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

In Theory
  • 131
  • 6