16
$\begingroup$

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!

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

3 Answers 3

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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? $\endgroup$
    – user13136
    Feb 18, 2013 at 9:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – usul
    Feb 18, 2013 at 17:54
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andrew D. King
    Feb 19, 2013 at 17:11
14
$\begingroup$

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.

Improve this answer
$\endgroup$
14
  • $\begingroup$ 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)$. $\endgroup$
    – user13136
    Feb 17, 2013 at 23:57
  • $\begingroup$ 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. $\endgroup$
    – user13136
    Feb 17, 2013 at 23:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Feb 18, 2013 at 13:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yoshio Okamoto
    Feb 18, 2013 at 13:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Feb 18, 2013 at 14:14
9
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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