There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard for general graphs.
Now, loosely speaking, in the case of the matching for general graphs, Edmond's Blossom Shrinking algorithm essentially reduces the general case to the bipartite by temporarily removing odd cycles via shrinking them to a single node.
It seems a natural questions as to whether Edmond's Blossom Shrinking algorithm could not also be adapted to yield better graph coloring algorithms, because in graph coloring, odd cycles are also the essential source of trouble.
A very simple initial idea could be to remove the root-nodes (as defined here) from blossoms prior to shrinking; that would finally result in a bipartite subgraph which could be colored trivially with two colors.
The further steps would be to repeat the algoritm for the subgraph induced by the temporarily removed roots and do the bicoloring with the next two available colors, until all conflicts are resolved.
Question:
are there already algorithms known, that are based on Blossom Shrinking and what would be the expected approximation class of such algorithms?
