I am a tourist of Graph theory but I have this problem I am trying to solve, part of a research objective connected to quantum computing.
I am trying to understand the relationship between:
the problem of minimizing the number of conflicts (edges) by using k colors to color the vertices of a graph $G$ (problem 1)
and
the identification of the largest induced subgraph of $G$ which is k-colorable (problem 2).
In particular, I would like to know if a solution to problem 2 can be found if I have access to all the solutions of problem 1.
In particular, I was interested in knowing if the following is true:
for at least one solution of problem 1, if I identify a minimum-vertex cover $V^\prime$ of the vertices that are in conflict - then I can remove $V^\prime$ from $G$ and get a valid solution to problem 2.
I am trying to find a counterexample to prove if this is false. Anyone has ideas?
$\endgroup$ 22 Answers
$\begingroup$It looks like your fact is true:
There is a $k$-coloring $\varphi$ of the vertices such that: if $S$ is a minimum vertex cover of the violated edges of $\varphi$, then $\overline S$ is a $k$-colorable induced subgraph of $G$ of largest possible size.
The relation between vertex covers and independent sets is actually extremely tight. Let $\varphi$ be any coloring of the vertices, and let $\widetilde G = (V, \widetilde E)$ be a new graph with the same vertex set, and edge set $\widetilde E$ equal to the violated edges of $\varphi$. Then vertex covers in $\widetilde G$ (i.e. covers of the violations of $\varphi$ in $G$) are exactly complements of independent sets in $\widetilde G$ (i.e. $k$-colored induced subgraphs of $G$). This implies that complementing a smallest vertex cover (across all colorings) will give a largest $k$-colorable subgraph (across all colorings).
It doesn't seem feasible to solve Problem 2 using solutions to Problem 1, however. Let's say a solution $\varphi$ to Problem 1 is a $k$-coloring of the graph that minimizes the number of conflicts. Problem 2 asks for the largest induced subgraph that's $k$-colorable, and as we saw above that's the complement of a minimum vertex cover of $\widetilde G$ for some coloring $\varphi'$. There are two problems: one, there's no efficient algorithm to find a minimum vertex cover of the violations of $\varphi$ if we're given $\varphi$ (it's NP-hard); two, the minimum vertex cover for $\varphi$ may not even be the smallest possible minimum vertex cover across all colorings.
$\endgroup$ 5 $\begingroup$AR: I thought about this question a bit and I hope it can be answered by forces of MSE users, because it may be not so hard, but it needs different ideas and approaches. Also it gives a unique occasion to find an application of such abstract and combinatorial branch of mathematics as graph coloring is such deep natural science as quantum computing, so I am happy to support it by finding at last a good use for a few of my reputation points. :-)
Thus my bounty increased the number of question views to 37 and a part of them are mine. :-) But I don’t give up. In September starts my regular season of intensive graph theory collaboration with the group of Sascha Wolff in Würzburg, and I’m going to propose your problem for our group. I hope it would be helpful because these guys are true graph theorists whereas I am a mathematician. :-) If we'll found an answer then I'll write it here. :-) Currently I can only say that for $k=1$ the answer is positive, but this is trivial. There is only one solution of Problem 1, and the largest induced one-colorable subgraph is the largest independent set, which is equivalent to a complement to a smallest vertex cover of the set of vertices with non-zero degree.
$\endgroup$ 2
