Timeline for Coloring a graph by Maximum Independent Set extraction

4 events

when toggle format	what		by	license	comment
Jan 8, 2013 at 17:02	comment	added	Andrew D. King		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.
Jan 8, 2013 at 1:21	comment	added	Alberto Rivelli		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.
Jan 8, 2013 at 1:09	comment	added	Alberto Rivelli		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.
Jan 7, 2013 at 20:08	history	answered	Andrew D. King	CC BY-SA 3.0