Precoloring extension

Precoloring extension is a natural generalization of graph coloring: we are given a graph where a subset of the vertices already have a color, we have to extend this precoloring to the whole graph (using the given number of colors). Clearly, this problem contains ordinary vertex coloring as a special case, hence it is NP-hard in general. Therefore most of the research considers restricted classes of graph where the problem might be easier.

I have compiled a small collection of links to online papers on precoloring extension. If you find that a relevant paper is missing or a link is wrong, then please mail me.

The restricted access sign means that full text can be accessed only if you or your institution is subscribed to the online service.

Maintained by Dániel Marx.
Last updated: October 29, 2007
Back to my homepage