Coloring a graph by Maximum Independent Set extraction

Question

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

Answer 1

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.

Answer 2

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