3
$\begingroup$

recursively extracting a MIS from an undirected simple graph $G$ does produce a minimal coloring for $G$ ?

I searched extensively the internet and found a paper [1] which answer partially to this question.
In this paper is shown a counterexample which is the graph depicted at the end of this post. In this graph if we extract the independent set $\{4,5,6\}$ we get necessarily a 4-colors coloring, while $\chi(G)=3$ for example by using the coloring $\{1,5,6\},\{2,4\},\{3\}$. However, it can be noted, that in this particular instance every minimum coloring can be produced from MIS extraction by selecting the proper MIS at every step.
So the question is, is there always at least one proper ordering of MIS extraction which results in a minimum coloring for $G$ ?

The answer should be no, because the following related simpler statement is false for a generic graph either, but I have no authoritative quotation for this.
"there exist a minimum coloring for $G$ in which one color class is a MIS for $G$ ?"

However it's easy to see that a coloring in which a color class is a MIS requires at most $\chi(G)+1$ colors:
Extract a MIS $S$ from $G$ and color it with the same color. We have $\chi(G)-1\le\chi(G\setminus S)\le\chi(G)$, so a minimum coloring for $G\setminus S$ plus the color used for $S$ is a feasible coloring for $G$ which uses at most $\chi(G)+1$ colors.

1---------2
|\       /|
| \     / |
|  \   /  |
|    3    |
|   /|\   |
|  / | \  |
| /  |  \ |
|/   |   \|
4    5    6

[1] S.I. Butenko, C.W. Commander, and P.M. Pardalos. On the complexity of the broadcast scheduling problem, University of Florida Technical Report, 2004

$\endgroup$

2 Answers 2

4
$\begingroup$

As you have seen, the answer to all of your questions is emphatically no. However, you may be interested to know that a similar colouring strategy has been studied, namely for the fractional chromatic number. This greedy fractional colouring approach was first studied by Reed; McDiarmid and later myself and Edwards gave improved analysis (http://arxiv.org/abs/1208.5188).

As for your statement that there is a $\chi+1$ colouring in which a colour class is a maximum stable set, this kind of misses the point. The approach of repeatedly removing maximum stable sets cannot be guaranteed to come within a constant $k$ of $\chi$. To see this, consider the example of a $k+2$ clique with two further $k+1$-cliques attached to every vertex of the first clique. This graph is clearly chordal and therefore $k+2$-colourable, but the recursive greedy algorithm will use $2k+3$ colours.

$\endgroup$
3
  • $\begingroup$ the simpler problem of finding a coloring in which a color class is a maximum independent set was introduced because its negative answer was enough to prove that the greedy mis extraction algorithm can fail. Yes my statement of $\chi+1$ was off-topic. Your example is correct, I've not concentrated on the approximation results but it's like the greedy extraction is "losing" some colors at every step, isn't it? I've notice this while searching for a counterexample, and I thought that may be there was no upper bound on the numbers of colors used by the algorithm. $\endgroup$ Jan 8, 2013 at 1:09
  • $\begingroup$ Anyway you confirm my answer is correct, right ? Just to be sure I didn't make any mistake, because I will put that counterexample in my thesis. Thanks. $\endgroup$ Jan 8, 2013 at 1:21
  • $\begingroup$ Yes, everything you are saying is correct. In these examples, notice that when we don't have a good colouring, it is because we take a maximum stable set that does not intersect every "hard to colour" region of the graph. In these cases the "hard to colour" region is a large clique, but you could also think of it as an induced subgraph with high chromatic number. The reason that Reed's approach gets a nice bound for the fractional chromatic number is that it doesn't just take any MIS, but rather it takes every MIS with equal probability. $\endgroup$ Jan 8, 2013 at 17:02
1
$\begingroup$

this counterexample really confirms that both answers to my questions are negative.
In this instance is easy to see that $\chi(G)=\alpha(G)=4$, $\{1,2,3,4\}$ is a complete graph and the maximum independent set is $\{5,6,7,8\}$.
A minimum coloring for $G$ put necessarily each vertex of the complete graph in a different color class but by taking one vertex of the complete graph the maximum size for an independent set is $3$, so there can't be a minimum coloring for $G$ in which a color class is the MIS.
Infact it's easy to see that if we take the MIS as a color class we need $5$ colors. And so the MIS extraction coloring is never a minimum coloring for $G$.

 
      5
     / \
  6-1---2-8
   \|\ /|/ 
    |\X/|
    |/X\|
    3---4
     \ /
      7
$\endgroup$

Your Answer

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

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