# Are vertex colourings--in a sense--edge colourings?

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!

• 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. Feb 19, 2013 at 9:13
• 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) Feb 21, 2013 at 8:52
• @vble: thank you! I admit that I wanted "too much". Such an operator would resolve Nishizeki and Zhou 's problem. Feb 22, 2013 at 19:00

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.

• 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? Feb 18, 2013 at 9:42
• @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, 2013 at 17:54
• 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. Feb 19, 2013 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.

• 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)$. Feb 17, 2013 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. Feb 17, 2013 at 23:58
• @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. Feb 18, 2013 at 13:28
• 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. Feb 18, 2013 at 13:52
• @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. Feb 18, 2013 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)$.