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 
sign means that
full text can be accessed only if you or your institution is
subscribed to the online service.
- A Note on Graph Coloring Extensions and List-Colorings, 2003
M. Axenovich
- You Can't
Paint Yourself into a Corner, 1998
M.O. Albertson
- Extending Graph Colorings Using No Extra Colors, 1999
M.O. Albertson, E.H, Moore
- Precoloring extension. I. Interval graphs, 1992
M. Biró, M. Hujter and Zs. Tuza
- Scheduling with
incompatible jobs, 1994
H.L. Bodlaender, K. Jansen,
G.J. Woeginger
- Exploring
the complexity boundary between coloring and list coloring, 2006
F. Bonomo, G. Durán, and Javier Marenco
- Approximate
Constrained Bipartite Edge Coloring, 2001
I. Caragiannis, A. Ferreira, Ch. Kaklamanis, S. Pérennes, P. Persiano
and H. Rivano
- The
complexity of completing partial Latin squares, 1984
C.J. Colbourn
- Preassignment
requirements in chromatic scheduling, 1997
D. de Werra and N. V. R. Mahadev
- On
completing latin squares, 2001
T. Easton and R.G. Parker
-
NP-completeness
of the edge precoloring extension problem on bipartite graphs,
2003
J. Fiala
-
On the Computational Complexity
of the Forcing Chromatic Number, 2005
F. Harary, W. Slany and O. Verbitsky
-
Precoloring extension II. Graph classes related to bipartite graphs, 1993
M. Hujter and Zs. Tuza
- Complexity results for the optimum cost chromatic partition problem, 1997
K. Jansen
- Generalized coloring for tree-like graphs, 1992
K. Jansen and P. Scheffler
- Precoloring Co-Meyniel
graphs, 2005
V. Jost, B. Lévêque and Frédéric Maffray
- Precoloring extension with fixed color bound, 1993
J. Kratochvíl
- Coloring precolored perfect graphs, 1998
J. Kratochvíl and A. Sebő
- New trends in the theory of graph colorings: Choosability and list coloring, 1998
J. Kratochvíl, Zs. Tuza, M. Voigt
-
NP-completeness of list coloring and precoloring extension on the edges of planar graphs, 2004
D. Marx
-
Precoloring extension on unit interval graphs, 2004
D. Marx
-
Parameterized coloring problems on chordal graphs, 2004
D. Marx
- Precoloring extension on chordal graphs, 2004
D. Marx
- Graph
Colorings with Local Constraints -- A Survey, 1997
Zs. Tuza
- A Colourful Theory on Graphs, 2002
Zs. Tuza
- A note on planar 5-list colouring, 2001
Zs. Tuza and M. Voigt
Maintained by Dániel Marx.
Last updated:
October 29, 2007
Back to my homepage